Message Tracking does not find the message I was expecting, where could it be?
This situation calls for additional sleuthing.  You need to understand your messaging environment and all the systems a message passes through on its way to the Exchange server.  Identify each and check any available logs.  Configuration and operation of routers, firewalls, mail gateways, even managed layer-3 switches can have an effect on inbound mail.
How widespread is this issue?  Does it affect all inbound messages, a significant number of inbound messages, or a small number of inbound messages?  Look for any consistencies (sending domain, sending address, receiving address).
Test inbound routing by sending yourself a message from an outside mail system (e.g. Yahoo, Hotmail, gMail).  Test by sending the affected user a message from that same outside system.
This scenario can get very complicated and vary greatly from environment to environment because you are dealing with any number of different devices and configurations.  Take it systematically, start at the outside and work your way in. Test each step, raise logging levels if necessary.