We have an Exchange 2007 environment, our ISP is actually what is called an ITC as we are a public school system. We ended up blacklisted for awhile due to a virus but after that was fixed all was well. Now, again we are having issues with Hotmail. We can reply to: any Hotmail message and it will be received. However, if we originate an email to a Hotmail address it goes into never-never land. Plus, there isn't any way that I can find to speak with technical support to fix this issue. There's a community forum but that's it. Any and all suggestions are appreciated.
At this point, we are not on a blacklist. Our domain is wilmington.k12.oh.us if you want to check also. In addition, I had our ITC add an SPF record for our mail server. Now, I'm pulling my hair out because it still isn't working.
I have also tried Telneting and it says the message is queued but is processed but our server. So, I'm guessing it is queued on their server.