Having tried to send emails to Hotmail accounts before, I know that although its anti-spam software isn't amazing (far from it :p ), it does have a habit of picking out messages whos headers are not correctly formed. Can you post the code that creates the emails please?
Also, you might wanna check the body and subject of the email to make sure that it doesn't have anything words like "marketing", "sex", "enlargment" etc.
[edit]Bad Piers! Read the posts before posting...[/edit]
Yeah, I know that this has been said earlier, but still post the code please.