Before we go off into aliases. It would be very helpful if we had a cleaner test case.

Do you by any chance have two people at the same outside company (i.e. Alice@External and Bob@External) where one sending you mail gets thru but the other fails?