Смотрите на dkim-milter. Подключение MTA через сокет и это может обработать подписание с отличающимися ключами. В тестировании разумного (4x Opteron, RAM 4G, диск Sata на 1-7200 об/мин) машина смогла обработать принятие, подписание, и поставить сообщений 5k менее чем через минуту.
MTA должен смочь использовать фильтры типа milter. Постфикс смог сделать так приблизительно начиная с 2,3 с различными уровнями поддержки.
Мы используем dkim-milter с постфиксом также, и делает то, что Вы хотите. Документация немного тесна, если я вспоминаю правильно, и наш парень использовал это практическое руководство.