Check your spam? Maybe your domain has been flagged for spam. Or maybe the ip address has? If you have a dedicated server usually you have your own ip address. sorta... often times dedicated servers will route through the same ip address. If some one else is working with the same ip as yours they might be spamming the entire internet with spam emails and have gotten your ip redflagged. This doesn't seem the case as the problem exists with all 3 hosts. To me is sounds like some one went and messed with your email settings in zen cart. Change your passwords and correct your settings.