Скорее всего это проблема хостинга. От него многое зависит. Может хостинг в спамлисте у гугля. Вот что можно сделать на строне prestashop - сделай заголовок письма английский, не рассылай массово, проверь кодировку писем, чтобы не было нечитаемых символов.