Whether you represent a party requesting email or producing it, the decisions you make on behalf of your client will depend, first and foremost, on the specific "protocol" used to produce, send, and store the emails at issue.
The four most common email protocols are POP, IMAP, MAPI, and HTTP. Even if you are using a consultant to help with electronic discovery, you should have a general understanding of these protocols. Knowing which protocol was used will help you to figure out where relevant information is most likely to be found.
With POP, emails are generally deleted from the server when they are transferred to a user's machine. With HTTP, emails don't reside on a user's machine at all (except, perhaps, in a cache), but are stored on an offsite server. Examples: Gmail and Hotmail. With IMAP and MAPI, selected emails might reside on users' machines, but all will generally be available on an onsite client-managed server.
Whenever possible, consider onsite servers first. As a sort of corporate nerve center, these servers are likely to contain the highest percentage of relevant information. Another advantage is that the information is contained in one place, rather than on a host of personal hard drives. This means you won't have to engage in the expense of doing forensic analysis to uncover deleted messages. Finally, email stored on a server is less likely to be altered after sending.
Of course, emails stored on a server (or backups of the server) may be too numerous to read one by one and will contain a high percentage of duplicates. A consultant can help you with software solutions to remove duplicates and search what's left by keyword.
Source note: Some of the information in this post was derived from "A practical guide to e-mail discovery," by Craig Ball, Trial, October 2005 (not available online).