A DIMM in one of our mail servers decided to break today… to make a long story short, I had to install a new imap on my own machine (as I switched incoming MXes) and with the new installation a new SSL key was created. Evolution (the MUA) of course kept on trying the old server key. DOH.
After quite some minutes of swearing, re-installing and doing various other pointless things, I deleted the very suspicious-looking “cert7.db” and “key3.db” files in ~/evolution. Problem solved. This should be somewhere in the Evolution UI or at the very least help system.