We have been having problems sending e-mails to a few addresses the last while' We get the dreaded "The e-mail account does not exist at the organization this message was sent to. Check the e-mail address, or contact the recipient directly to find out the correct address." message.
We have solved most of them so far - found out they USED to be hosted on MegaMailServer through Rogers.com - but had moved and their record had not been removed from the sendmail record by Rogers. (the account we are sending this email from is hosted on MegaMailServers as well)
We are having the same problem with another address right now - they are hosted on MegaMailServer through a different hosting company, who I have contacted, and they claim the address I am sending to does not exist on that domain - yet I can send emails to that address when using my own (not MegaMailServer-hosted) email adress.