I'm making a site in which users will login with OpenID. I'll though, only give them the choice of Google, Yahoo, and AOL. They'll login or signup with their OpenID providers' accounts (Google/Yahoo/AOL) and after they are redirected back to my website, I'll show them "Sign up successful!", while in the meanwhile, I'll be storing their email-ID against their claimed-id or whatever that Google and the like give in OpenID AX (attribute exchange).
Now, due to some activities on the site, like comments, queries, etc, I want the user to be notified. For that I'd be sending mails to his email account I'd get from his OpenID signup for my site. And I will need the email-id to be in plaintext (obviously), to send them the mail. But in the database, I want to store the email-id securely, secure enough so that even if someone hacks and downloads the user table, they can't decipher email-id.
How to do that? For AES encryption or the like, I'd need to store a key. And if the backend scripts can have easy access to the key to convert the email-IDs to plaintext, then can't the hacker too?
I simply want to securely store the email-IDs of my site's registered users, and also email them about notifications, but without risking their email-IDs getting easily accessible by hackers.
As you described, absolute security is impossible. If you can read the email addresses (or any other data) on the server, potential attacker also can. Work on server and database security in order to bring the possibility of successful attack to a minimum.
Paranoid version is to take away email database to a different, physically separated, dedicated database server. The only data stored there should be user_id-email pairs. Don't run any other services on this server. Don't allow direct access to data - instead, hide it behind an API (stored procedures maybe) with two methods:
Again, this will never be 100% secure, but just provides another layer of defense.