So i’ve got to troubleshoot this issue in a very complex multi-domain & multiple exchange organizations & servers..
Internal Messages from Server A in ExchangeORG A , were failing in the categorizer while being processed to be sent to Server B in ExchangeORG B.
Following kb884996 , resolution 2 was valid in my situation, Allow inheritable permissions from parent to propagate to this object check box on Server A object, was missing a Tick..
I set this via ADSIEDIT , noticed of course that the “Exchange Domain Servers” ACE entries , from the other domain were added, and allowed for replication.
After verifying that the ACE’s were propegated & fully replicated, I did a quick restart to MTA, Routing & SMTP services on both servers , and operation was succesfully restored.
Just for extra , this could be also issues with Event Sink that might have been registered and inproperly removed / integrated.. using the smtpreg.vbs , “cscript smtpreg.vbs /enum > Output.txt” i was able to verify that no 3rd party Event Sink were installed or any of Exchange Event Sinks were disabled…
More Links on the Subject:
Troubleshooting messages stuck in ‘Messages awaiting directory lookup’ queue
How to troubleshoot messages that remain in the “Messages awaiting directory lookup” queue in Exchange Server 2003 and in Exchange 2000 Server
Directory service server detection and DSAccess usage