milonholik, а адрес тот, что надо, отправляет? или мыло сервера?

Поюзай со своего сервака mail(); с разными параметрами. возможно приоритетом не угодил, либо неправильные заголовки. Попробуй на мыло спейса отправить, там всё через ж... работает, возможно увидишь причину. проверь на другом хосте/движке работу с мылом.