If your webserver still thinks that it has email on the same server, it may mistakenly be routing everything through itself instead of through the newly-established server.
Zen Cart just hands off the mail to the mailserver, and it's the mailserver that handles all the sending including looking up mx details etc.

I would recommend that your server administrator be the one to sort out your mail routing issues.