Mail sent from Outlook client not hitting Exhange 2007

Mails showing up on Outlook client as sent but not being delivered to recipient.
Investigating the Message Tracking in Exchange 2007 the mail does not show up, and there is nothing in the queue.

This only happen to some mail. All other mail is delivered OK from Outlook client to recipient

Is there anything else i can check?