Judging from the long list of exim4 bugs, especially #446036, I find myself between a rock and a hard place, and having to choose between staying with GnuTLS and accepting a probably continuing flow of technical issues, or moving over to OpenSSL, setting an example against GNU software, and probably generating a new flow of license issues.
exim4, sarge's default MTA, uses gnutls for the obvious license reasons. However, gnutls does seem to have issues of interoperability, which have manifested themselves in a list of bugs, most prominently being #297174, which we are at a loss to debug.
Neither Andreas nor me have the knowhow to debug gnutls, and Upstream uses openssl - the gnutls patch was contributed and the author of the original patch doesn't seem to be around any more.