Do the registration mail also go to your email archive? If you can see them there, it means Zen Cart is sending them. You may need to contact your host and figure out why the mails aren't leaving the server.
Yes, the registration emails do go to the email archive. I have submitted a support request with the host to see what they say. The weird thing is that the direct email does go out successfully.. so it's not a case of no emails go out, but just the automated ones aren't going out. (or, more specifically, being received).

What extension does the email address have? (After @) there are some email "hosts" that do not work well for sending emails.
Also, when trying each of the other methods, what were the settings (don't post your credentials, but do identify that credentials were set, etc...)
One test account uses a gmail account, another test account uses my own domain email. The smtp details were as per the host suggested configuration.

Thanks