>You could always hash the e-mails, although this would make resetting your password impossible.

Not really - everywhere I've gone has asked me for my email to send me my password. Same principle as with passwords: enter your email, we hash it, if it matches a hashed email in the DB, we send a 'reset' email to the address you entered.