В ответ на: Я обычно в таких случаях делаю простейший скрипт чисто отправляющий письмо, например, и тыкаю его хостеру под нос.
Если начинает вякать "починка скрипта - не наша забота" - выкладываю это же скрипт на другой хосттинг и говорю "вот тут - работает, а вас - нет, вы все еще настаиваете, что проблема в скрипте?!"
Обычно этого достаточно.
Хороший повод поменять хостера.