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
ehlo from_me.com
mail from:<[email protected]>
rcpt to:<someone@the_domain.com>

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.

Steve