Если ваш веб-хост не позволяет отправлять исходящую SMTP-почту со своих серверов, это может привести к этой проблеме. Например, GoDaddy позволяет только отправлять исходящую почту через smtpout.secureserver.net с вашего сервера, поэтому любая попытка отправить почту через другой хост (в данном случае smtp.gmail.com) будет неудачной. Если ваш провайдер не блокирует исходящий SMTP (как, например, Qwest), то это будет работать локально.
Проверьте FAQ с вашим веб-хостом, чтобы увидеть, что они говорят об этом. Большинство хостинговых компаний разрешают исходящий SMTP, но ограничивают его определенным количеством ретрансляторов в день, чтобы предотвратить случайную эксплуатацию для пересылки спама.
Вы правы, что запись MX на вашем домене влияет только на входящую почту. Когда кто-то пытается отправить письмо на адрес you@yourdomain.com, он передает его SMTP-серверу (скорее всего, тому, который ему предоставляет провайдер), а затем SMTP-сервер просматривает вашу запись MX, чтобы узнать, кто обрабатывает вашу электронную почту. Это разрешит smtp.gmail.com, так что это кто получит вашу почту, а вы получите ее. Когда вы отправляете исходящую почту, она может проходить через кого угодно, так как вы заботитесь только о записи MX для домена назначения (где почта в конечном итоге окажется).
Это имеет смысл? Если вам нужны некоторые разъяснения, я могу найти некоторые учебники и другие объяснения, которые помогут разобраться в этом.