При перемене IP aдресов списков рассылки они записываются в blacklist различных почтовых серверов, например mail.ru Пожалуйста - предупреждайте заранее о переездах рассылок на новый IP адрес - выставите для них нормальные DomainKeys.
Кстати spf-запись тоже неплохо бы прописать.
У меня немного другая проблема, но видимо в этот же баг. Мэйл.ру режет *часть* писем, вероятно, считает спамом, точно можно узнать у mailman-а. Причем добавление *@lists.altlinux.ru в whitelist не помогает. (Ну естественно, from-то не оттуда). Хорошо бы убедить mail.ru (и другие подобные сервисы), что мы хорошие и спам не рассылаем. Может, им в абузу письмо написать? Не очень понимаю, что именно писать туда...
Когда будут конкретные предложения, откройте.