Проблема началась с того, что сервер через раз стал отправлять письма с помощью стандартной php функции mail(). Стал смотреть что не так с почтовиком exim4. И оказалось что у него очередь скопилась в 450 сообщений, среди которых были и нормальные. Все сообщения были помечены как frozen. Немного полезных команд для exim:
Узнать кол-во сообщений в очереди:
Вывести список очереди:
Узнать кол-во сообщений в очереди:
exim -bpc
Вывести список очереди:
exim -bp