I've had the same problem with my private domain e-mail. Finally got something to work.
Try this:
When the annoying little window pops up telling you it can't verify... blah, blah, blah, click to show more details below.
Check the "Always trust..." box AND
Go down to where there are three other selections as well. Mine already said Always Trust.
Change the top one to "Use User Defaults" or what ever it says at the top of the drop down.
Restart Mail and see if if comes up again. Mine seems exorcised but who knows what lurks after a reboot.
Blessings,
Jonathan