Message Tracking shows external email recieved in ESM but does not deliver to client mailbox

We have inconsistently recieved emails from First_Lastname/xxxx/xxxx@notes.xxx.xx.xx

Although it shows up in our ESM, however email is not delivered to the recipients mailbox as shown:

Message History
5/17/2006  4:15pm SMTP:Message Submitted to Advance Queing
5/17/2006  4:15pm SMTP:Started Message Submission to Advanced Queue
5/17/2006  4:15pm SMTP:Message Submitted to Categorizer
5/17/2006  4:15pm SMTP:Message Categorized and Queued for Routing
5/17/2006  4:15pm SMTP:Message Queued for Delivery
5/17/2006  4:15pm SMTP:Message Delivered Locally to xxxx@company.com
5/17/2006  4:15pm SMTP:Store Driver:  Message Delivered Locally to Store to xxxx@company.com

Sender claims they are sending emails two methods:
method 1:  via new mail messages works fine and can send/recieve all the time.
method 2: via notes calendar works inconsistently

Sender is using lotus notes email system.  We are on MS Exchange 2003.

Please help.