Mails not getting to some external recipients

[lmoniz]

This problem has me tearing my hair out. I have some internal people trying to send messages to external addresses. The logs for the mta and gwia show the messages transferring without error, the mta is even logging a confirmation bit.
Messages were going out for a while and then started to not be delivered tot he external addresses. I figured a spam or rbl listing on the recipient's side. The problem continued so I rebuilt each mailbox with gwcheck, rebuilt address books, removed frequent contacts but still no joy.

Did a top down rebuild while at the same time communicating with some of the recipients and mail started to go through again. Mails have now stopped being delivered once again. All logs at my end show the messages being delivered to the receiving servers and no errors that I can see. I'm still convinced that the problems are happening after the messages leave my server but I want to ask if there are any obscure settings that I might be missing that would contribute to this problem. To make things more difficult, there are no bounce back messages from the recipient servers either.