Ok that means:
- It didnt go through the Exchange pipeline. i.e. if they have another account added to their profile
- Something is broken. If not 1 - then open a ticket with 365 support. Every message sent through the ExO transport MUST be visible in the message trace logs except for some system type messages.