After renewing Exchange certificates IMAP stops working

The strangest things happen as an Exchange admin.
Recently i renewed the certificates for our Exchange servers, and while everything went fine the next day we got several calls that a few IMAP mailboxes stopped working.

No this is particularly strange because it's an IMAP mailbox that uses plain text logon on port 143, the default imap port so it doesn't even use a certificate.
After ripping my hairs out, calling everybody who came to close a #$%^ and a &!@#*& i came across this post by Jetze Mellema.

Strangely enough it worked, well at least for 2 of the 3 mailboxes.
The day after we were getting calls that there was still one mailbox that couldn't connect.

Same error in the IMAP protocol log:

2016-12-13T09:11:57.785Z,000000000000003F,8,x.x.x.151:143,x.x.x.202:54194,imapmailbox,63,43,55,login,imapmailbox@domain.com *****,"R=""2yc2 NO LOGIN failed.\r\n* BYE Connection is closed. 14"";Msg=Proxy:servername.domain.lan:1993:SSL;ErrMsg=ProxyNotAuthenticated"

The error message suggests that there is something going on with authentication or a firewall issue possibly blocking a port or using a certificate that is expired or has wrong name in it.

But no, to solve this we moved the mailbox to another mailbox database.
After the move we created an Outlook profile with the correct credentials and were able to login immediately. 

Now if you're reading this and you know why this happend please let me know, because i was baffled and totally don't understand any logic behind this stuff.