Parece ser um bug no lado do hotmail. Eu tenho o mesmo problema que você desde 3 meses, alguns domínios com os mesmos registros spf do que outros domínios, estão falhando com senderid = temperror.
Eu escrevi para o hotmail, eles me dizem que é um bug do lado deles (talvez no cache do dns), e eles estão trabalhando "ativamente" para resolvê-lo ...
o hotmail é uma merda ....