Проблема решена. Спасибо суппорту мейл.ру.

С субботы, 10 октября 2009 года, письма нашего сервиса перестали доходить до пользователей сервиса Mail.ru и иже с ними (inbox и другие).  Сервер просто не принимает эти письма, возвращая 550 ошибку:
smtp;550 spam message rejected. Please visit http://mail.ru/notspam/ or report details to abuse@corp.mail.ru.
Поэтому, обращаем ваше внимание, что могут «не доходить» письма с подтверждением регистрации, а для [...]