Sergey

SPF-то не сделал, судя по заголовкам.

Да, такая ситуация возникает из-за того, что на странице смешанное содержимое, https+http. Чаще всего это картинки/фреймы в письмах.

Гмейл не обучается на ваших конкретных письмах для вашего конкретного ящика, помечая письмо как спам, вы просто отправляете его в «общий котёл», где по неким сложным механизмам, задействующим мат.статистику и прочую нечисть, обучается распознавать спам «в целом».
Насчет «перезапуска». Такой функции нет.

Не бойтесь, хостинг DNS и хостинг сайта могут быть никак между собой не связаны.
Просто покупайте хостинг ДНС, этой услугой многие торгуют. Либо можно и бесплатными сервисами пользоваться, если у вас мало доменов. Здесь, в Q&A было уже несколько вопросов по выбору ДНС-хостинга, поищите поиском. Многие рекомендуют яндекс, там можно и без привязки почты к ним хостить свои домены на их ДНС-серверах, бесплатно.

Забавная ссылка. Двое русских на буржуйском ресурсе поболтали на английском )
Не припоминаю никаких проблем с гугловским пушем на айфоне 3Г с прошивкой 3.х. У вас какой девайс-то?
На андройде нет проблем.