Реально ли как-нибудь по средствам php, отправлять почту другим образом кроме как mail(), поскольку скорей всего хостинг на котором размещён сайт находиться в чёрном списке большинства почтовиков. То нужно искать альтернативный способ отправки писем.

То что проблема в хосте это 100%, т.к. на другом сайте этот же скрипт работает на УРА!

Если это так, то даже если вы бы использовали какие-либо другие функции или классы, то это ситуации никак не изменит. Шлите письма через промежуточный шлюз какой-нибудь или свой почтовый сервер.

Ремарка. То, что дело в хостинге (платном) кажется очень и очень маловероятным.

Zuldek
Одни и теже email, один и тот же скрипт 1 в 1. На одном хосте отправляет, На другом нет. В чём ещё может быть дело кроме как в хосте?