So, sendmail is the blackest of all black arts and the configuration is designed to confise you. I HATE sendmail as it is sooo confusing and my small mind gets overloaded. I don't know your level of knowledge so forgive me if I teach you how to suck eggs here or I tell you something that is not 100% correct, but here goes:
The error message mentions an MX record that performs the redirect and that delivery fails. This means that the server to which the MX record points does not exist in DNS, or it is not running an SMTP server, or that this server is actually a local alias to your server?
Assuming that your machine is unix-like (you say linux?) then check the /etc/nsswitch.conf file (or equiv) to see what the entry for 'hosts' says. If it mentions 'dns' then sendmail may be using the MX records in your local DNS servers to decide on how to route the emails.
Check the /etc/resolv.conf (or equiv) and find out where the DNS servers in use are. If they are on your machine (you say it does DNS services) or a machine that you are in control of then have a look at the MX records - these are DNS entries used to decide on how to convert an SMTP mail domain name to a DNS domain name (I think it is that but welcome a more accurate description!?).
It looks like your DNS servers have an MX record that tries to route mails coming from the users of your sendmail instance, when they send any mails to deleteddomain.com, to the mail server at
www.myserver.com.
I ASSUME (I try to avoid sendmail so know very little about all the files you mentioned) that there is a problem with contacting a mailserver at
www.myserver.com, or that the nslookup for this name fails or the IP address for this name does not respond or that
www.myserver.com is actually a name that resolves locally and therefore your sendmail application should accept mails to this domain but it does not.
?