Подстановочный SPF должен в работе теории (http://tools.ietf.org/html/rfc4408#section-3.1.5), но действительность - то, что это не полностью надежно. Не слишком трудно установить отдельные записи на домен в форме
v=spf1 a mx a:mx1.example1.com a:mx1.example2.com a:mx1.example3.com ~all
но некоторые установки DNS имеют предел количества серверов, которые Вы имеете. Может быть лучше сделать это IP-адресом, если домены размещаются на том же поле. Даст меньше обслуживания.
Попытайтесь установить подстановочный рекорд для В TXT, например:
* IN TXT "v=spf1 -all"