Unfortunately, the only consolation on Gmail doing such things is that Hotmail is usually worse. It's not just a Zencart problem, it's fairly universal.
If you are with a hosting service, it could be that their mail servers are blacklisted, or if you are sending from a non hosted environment, be aware that most home broadband connections are almost automatically blacklisted.
The other common problem is badly formed headers on the email - wrongly specified encoding and charsets, and mail originating from Apache server user nobody. Check the headers of the bounced mail.





