I have been fighting against this for a couple of days now, and have fianlly solved it. I make no claims that this is a defiantive solution, but it worked for me.
I think part of what made things difficult was that there are regularly two problems here.
Microsoft are pretty tight on their anti spam controls. You need to make sure you have correctly configured SPF records the domain you are sending from.
Microsoft provide a wizard to help you to create a valid SPF record here. It will also verify an existing SPF record for correctness,
When you have got your record set up, you should validate that all is using the auth verifier here.
You should try to subscribe a dummy user, with the email address supplied above.
When you get the mail back, if it says you have passed the senderid check then you can move on.
e.g. successful senderid check looks like this.
Summary of Results
SPF check: pass
DomainKeys check: neutral
DKIM check: neutral
Sender-ID check: pass
You should now go to dnsreport.com, and check out the domain you are sending from. There should ideally be no red on this report.
When you pass, and not before you should send a mail to email@example.com, with the domain you are mailing from in the body of the mail. A couple of days later you should get a mail back to say that you have been added to the senderid programme. (I had to send this mail from a hotmail account to get it not to bounce!!)
You should now be able to send registrations and other mail to hotmail,msn and livemail addresses.
However, this does not always work, which brings me on to.
By default Joomla used the PHP mail function to send emails. This is configured in Site->global configuration->mail tab.
For some reason hotmail does not seem to like the headers produced by the default config.
To get things going configure and use an SMTP server. (In most cases localhost)
These two tips have got my mail through from three problem domains.
I hope they work for you too.