Вопрос: у тебя mail на какой основе сделан - встроенной в PHP ф-ции sendmail или нет?
------------ Дoбавленo:

Если ДА - то заказываю: переделать под PEAR::Mail class (пример - тут)