outlook.com outgoing blacklists?

["Todd K Grand" <tgrand () tgrand com>]

I have an email server which hosts 3 domains.
I have reason to believe that microsoft maintains an outgoing blacklist and would like confirmation on this.

I have had many a report that people on domains hosted on hotmail/outlook are getting messages bounced back stating 
that our server was unreachable.
This only happens for one of the three domains hosted on our server.

I went to outlook.com and setup an account.
When I create a new message and enter the recipient at that affected domain, the address immediately turns red, and 
when I hover over it states that
the address may not be valid.
This happens without ever sending a packet to our servers.
The affected domain can send emails to hotmail/outlook accounts just fine.

Anybody have some recommendations on how I resolve this, as Microsoft support seems to be under technical.

Thanks,

Todd K. Grand