Another good way is if you have customer name and address, is to find an email append service. they charge a few cents per match. For a couple hundred bucks, depending on your database size, you might match up 30 - 40% of what you are missing in a matter of hours..
I have NEVER been able to get an email append to work (show a valid response rate/roi)
And, I dont think they are just a few pennies. Last I checked they were closer to $1 for email appends.