Hi wormcounter,
Are the emails sent by your outlook, your web site, or both?
Do you have your own mail server or are you using your ISP's outgoing smtp server?
Check the log files on the outgoing mail server.
If it's a shared relay it could be a problem with another user that is spamming which would cause Hotmail to block all email from that smtp relay
You can configure additional From: email addresses in your Gmail account.
Once that is done you can send From: your business email address with Gmail.