Is it possible your mail service can use port 587? I don't know how many exit nodes allow that (nor do I know how to quickly check), but I'm using 587 with SMTP over SSL, and it seems to work fine. Check my headers if you don't believe me. :-)
Just tested this and it works (of course Murphy made sure that port 25 was also happily working tonight). I'll probably have to look into one more thing since I think most of the time I'm having problems seems to be on my laptop at the office. Worse come to worst, I guess I will just have to go back to using TOR with the domain's webmail. Been trying to avoid this since web mail is typically snail paced and going through TOR means additional latency plus pointless html traffic for the onion network.