At some point, you need to check the email server. Both the sender and the recipient could have deleted the relevant emails, but there is a good chance a copy is still on the email server. Many servers have a retention policy, which may be governed by law in certain industries. When you examine an email server, be aware that a variety of email server programs could be in use. Microsoft Exchange is a very common server. Lotus Notes and Novell GroupWise are also popular email server products.
The file extensions associated with the most widely used email server software are listed here:
Exchange Server (.edb)
Exchange Public Folders (pub.edb)
Exchange Private Folders (priv.edb)
Streaming Data (priv.stm)
Lotus Notes (.nsf)
GroupWise (.db)
GroupWise Post Office Database (wphost.db)
GroupWise User Databases (userxxx.db)
Linux EMail Server (Logs/var/log/mail.*)
Obviously, tools like Forensic Toolkit and EnCase allow you to add these files to a case and to work with them. You can also manually examine these files, provided you have access to the relevant software (for example, Exchange or Lotus Notes).