Hi Carl,
The first thing to check is the mail logs on your server to get the exact error messages and look for signs of an ongoing spam problem.
There are a few likely sources of the spam including infected workstations in your network, a compromised form on a web site, compromised user credentials, an accidental open relay, and/or backscatter.
After you find and fix the problem monitor your
sender score. When you score is back above 60 use this information to open a ticket with Microsoft -
Hotmail Blacklist