Exchange Server 2003 & Finding emails

I’m in a position where a network I administer is asking me to locate all email from/to a specific external individual within a certain date range. I used MS Tracking in the System Manager and came up blank. I know, as does the client, that several emails should exist.

The enduser admits deleting the emails from his workstation(Outlook 2003). Circumstances are such that those email are despirately needing to be located to verify a legal claim.

My question is: How can I do a thorough search of the Exchange 2003 data that will include all email ever sent from and received by the server?

I have the specific email address and the date range.