Можно хранить не адреса почты, а их MD5 хэш (по хэшу узнать адрес нереально). 
  
Но спаммеры при помощи ботнетов могут сделать "накрутку" такой базы, так что это сразу надо учитывать.
  
Было бы неплохо иметь сотню таких БД и интеллектуальную систему автоматического выбора каким серверам больше доверять, каким меньше. И сделать ПО серверов открытым.
		
		Но спаммеры при помощи ботнетов могут сделать "накрутку" такой базы, так что это сразу надо учитывать.
Было бы неплохо иметь сотню таких БД и интеллектуальную систему автоматического выбора каким серверам больше доверять, каким меньше. И сделать ПО серверов открытым.

 Это практически 100% способ заставить отказаться человека от своего емайла, как бы он не был ему дорог