Are you getting any NDR's or errors of any kind or do the messages seem to go, and you get no errors nor NDR's, but the recipient never receives the message(s)?
Is it the same recipient domains all the time and every time?
Use the message tracking tool to make sure that the messages leave your Exchange Org. If so, then you may not comply with email sending best practices and may be blocked by anti-spam rules. Chances are if you are truly blacklisted, you'd know it by now, but individual organizations could be denying delivery due to lack of compliance and wouldn't necessarily notify you.
It's kindof a broad assumption at this point, so I won't go into the detail yet -- HELO/EHLO server name, reverse DNS, sending from static IP vs. dynamic IP, etc., etc.
--C