you need to create a TXT record for all your domains (not sure if you can just do it for you mail domain, but i found you need it on each one. It is a special Sender ID SPF record, they come from Microsoft to fight spam.
They seem quite complicated build up, this is mine for example:
v=spf1 a mx ptr ip4:87.XX.XX.XX mx:liYY.YYY.com ?all
XX is mail server ip
YY are mail server PTR record.

After some hunting around I found that dear Microsoft actually provides a tool to create these TXT records, pretty nice! it also Test your domain if it is ok or not (you can do this instead of dnsstuff.com)

http://www.microsoft.com/mscorp/safe...d/default.aspx