Proof of delivery

Hello all,

Someone says they sent us an e-mail months ago to one of our "main Mailboxes" that we did not see or find in our exchange server. We have e-mails from that "mailbox" that go back a couple of years  in ".PST" files that were moved from the server to save on space. We did not find that e-mail in the PST files either. They provided a "log" from their"email content gateway" (Mail Marshal) that supposedly confirms that it was delivered to our server. Our server was a Windows 2003 server with exchange 2003 that we just migrated (about a month ago) to a Windows 2008 R2 server with exchange 2010.

My questions are :
How can I officially confirm (and have proof) that the e-mail did not reach our servers? Does exchange 2003 have a feature I can use to see if it did reach the server and would I be able to use it now in the new server since it was migrated?
How reliable is this "Log" they provided and is it real proof?
What software (or service in exchange 2010) can I use to keep these type of records in the future to give actual proof that e-mails Did/didn't get delivered?
We have not decommissioned the old 2003 server yet so I would be able to get to it if needed.

Thank you in advance for your help! It's much appreciated!