у нас была такая же проблема... первое на что стоит посмотреть, есть ли в настройках пхп smtp сервер, он может быть не прописан кривыми админами... второе, почему могут не доходить письма - это фильтр заголовков писем на smtp сервере, у нас как раз это и было, в почтовом шаблоне поставьте тип текст а не хтмл, может поможет...
попробуйте вызвать пхп файлом функцию mail() с различными заголовками вручную, может прояснится проблема...
попробуйте, если все это не поможет, будем думать дальше ;)