Ich habe starke Zweifel an dieser Aussage. Wenn der Support die Logs des Mail-Servers angesehen hätte, dann würde er dir exakt sagen können, wieso Google die E-Mails ablehnt. Google verwirft meinem wissen nach E-Mails nicht einfach so, sondern gibt immer eine Rückmeldung mit dem Grund.
Hast du in den Shopinformationen unter Allgemein und in den E-Mail-Einstellungen die gleiche E-Mail-Adresse angegeben?