Thanks both for the ideas and suggestions, there is plenty there for me to investigate and try. all suggestions could be the culprit really so I'll play around a bit.
It's not a critical thing in this case, as the mails go through to the client's inbox fine as they dont use hotmail. It was when testing myself and using my hotmail account that I had the issue. It would of course be a problem for various other projects though.
I'll email microsoft themselves as I guess they would be best placed to make a call on what the problem could be. they may even be able to check their logs and spot the rejected mails themselves. I'll also contact the host to check smpt stuff as suggested too.
I'll update the thread if I get a solution incase anyone else has the issue.