So that's the key point. If those messages arent making it to you, then its up to the sender to prove your org accepted it in their logs.
if a NDR exists, then even better.
Having said all that, does Exchange accept mail directly from the internet or is there a SMTP gateway that accepts it first, then routes to Exchange?