JustForComment,
I apologise for posting this out of context, but I don't know how else to make sure you see this. I came across an old question from a year ago about Apple mail client. I had the same problem you described, and I just found the reason why my client was "unable to verify" whenever the server's legitimate certificate was renewed. The one where you have to remove and re-add account to 'fix'.
All the normal checks to the server would show that the new cert was installed. Still the mail client would insist on showing me the old cert. As if it was magically cached somehow. (btw, it isn't)
The only way I could figure out how to reproduce the problem is by demonstrating three different types of TLS connections to the IMAP server. I found that when you introduce the SNI extension to the initial request it would actually reply with the old cert instead of the new. So two out of three methods worked, just using SNI made it misbehave.
Replace imap.virtualhost.com with your incoming mail server DNS name. Use the server's IP for realhost.com .
SSL/TLS: (works, sends renewed cert)
openssl s_client -connect imap.virtualhost.com:993
STARTTLS: (works, sends renewed cert)
openssl s_client -connect imap.virtualhost.com:143 -starttls imap
SSL/TLS with SNI extension: (broken, sends expired cert)
openssl s_client -servername imap.virtualhost.com -tlsextdebug -connect realhost.com:993
I hope this information will be enough to convince your provider that they need to find their misconfiguration and fix it.