Have you referred to Microsoft articles 823489 and 257265? Both provide a good starting point for troubleshooting transport issues. I also use message tracking to pinpoint specific transport problems.
You may also want to look at the DNS configuration for your Exchange server. I have had messages caught in the message categorizer due to the categorizer being unable to resolve the correct DNS record. You can use the DNS Resolver to determine if DNS is configured correctly (In TechNet search for “How to Use the DNS Resolver to Verify DNS Configuration.” part of the Exchange Server Transport and Routing Guide.)