Mail.app wouldn't stop asking about the certificates.

So:

Remove any instances of them from Keychain Access
Try to get mail - when told about the certificate choose View certificate and drag the icon to the desktop
Don't add the cert to your login keychain - drag it to the X509Anchors chain instead.
Mark it as always trusted (after all - you trust yourself don't you?)
Repeat 2. - 4. for sending mail.

Bingo! Well - works4me at least.