I knew that Microsoft’s Sender ID wasn’t a perfectly implemented solution, but I never investigated why. Now I know. Because despite using a dedicated company to send our mails through (SendGrid at this moment), we still got a bounce saying “Sender ID (PRA) Not Permitted”.
The reason is that Microsoft uses the SPF policies wrong. You can read all about it at the SPF vs Sender ID article. From what I understand from this article, all you have to do is add an extra TXT record to the DNS of your domain, with the contents “spf2.0/pra”.
Microsoft’s Sender ID Framework SPF Record Wizard recommends “spf2.0/pra ?all” though, so I went with that.
Of course you need to have already working SPF records for this to work.