So I was worried I did not know "exactly" how MX records are used so I looked em up:
http://en.wikipedia.org/wiki/MX_Record
This should help you figure out your routing problems, you seem to have been looking the the SMTP server's configuration to find the problem when the root cause appears to be related to an entry in the DNS configuration available to your SMTP server.
For the sake of argument:
"SMTP Server"="mail agent"="mail server"=sendmail process.
...and just in case for some reason your /etc/hosts file is being used in this process, check there are no entries in it that refer to deleteddomain.com and
www.myserver.com.