Thanks marco for your response. I had a look around but wasn't overly pleased with the support microsoft gave.
However having spoken to others i managed to solve the problem. My problem was that the domain did not have a valid SPF record.
My suggestions for anyone who has this problem is to do the following:
Goto dnsreport.com and get a report for your domain, or use the link below but replace example.com with your domain name.
Code:
http://www.dnsreport.com/tools/dnsreport.ch?domain=example.com
Then, deal with any RED coloured problems you have, and deal with all the YELLOW warning you have in the mail section. Inevitably, dealing with these individual problems will mean more googling around, but it beats having to search for a 550 problem.
Hope that helps