It actually has nothing to do with Zen Cart or the unroutable domains I was sending mail to. It has to do with cPanel configuration.
In cPanel, when you log in as the root user, there is an area entitled "Tweak Settings." Within this area, there is a section for tweaking email settings. Well, there was one particular checkbox that was checked which said, "Prevent the user 'nobody' from sending out mail to remote addresses (php and cgi scripts generally run as nobody if you are not using phpsuexec and suexec respectively.)"
That was why all my mail was coming from nobody@server1.mmyssite.com, and this is also why 99% of the ISP's were rejecting it. Apparantly, receiving mail from "nobody" is automatically blocked. So all I did was uncheck this option so that mail would NOT come from the nobody account, and now everything is working fine.
You may have to contact your host to have them uncheck this option for you, since you most likely cannot log in as "root" to your cPanel area.
You may also then need to use the sendmail -f transport method for sending emails.
Another setting in Zen Cart which may help you get around this "nobody" switch is the "Emails must send from known domain". If you enable this option, then Zen Cart will attempt to generate emails which will not be blocked by this setting.
