Do you speak SMTP?
Get the MX record for the_domain.com for example smtp.the_domain.com
then from a bash prompt type:
telnet smtp.the_domain.com 25
if you get a "user unknown" message here then that's an indication the mail doesn't exist
next type "quit"
And the connection will be broken, without any mail having been sent regardless.
Just an idea.