Why would you need to store a unique identifier for each email you send? You just need a unique identifier for each user, as settings would surely be user-specific.
Typically, email subscription settings wouldn't be considered high-risk or high-security - after all, they can simply resubscribe if they want the email. I would encrypt the user's id (and maybe their email address or some other salt) to give each user a unique unsubscribe key that is added into a link in the footer of each email.
Storing a unique key per user in a database shouldn't concern you. Chances are if you have the resources to send mass mailings on a regular bases, you have the resources to store a 32 character key.
The preference you observe looks like a natural consequence of recommendation clearly stated in GNU Coding Standards. It suggests to report bugs by email, as you can see in below quote (I marked bold the part that directly addresses your observations):
4.7.2 --help
The standard --help option should output brief documentation for how to invoke the program, on standard output, then exit successfully. Other options and arguments should be ignored once this is seen, and the program should not perform its normal function.
Near the end of the ‘--help’ option’s output, please place lines giving the email address for bug reports, the package’s home page (normally ‘http://www.gnu.org/software/pkg’, and the general page for help using GNU programs. The format should be like this:
Report bugs to: mailing-address
pkg home page: <http://www.gnu.org/software/pkg/>
General help using GNU software: <http://www.gnu.org/gethelp/>
It is ok to mention other appropriate mailing lists and web pages.
Above preference, in turn, reflects universal acceptance of email as a form of electronic communication. Any user reading --help message like suggested above is supposed to easily understand what to do if they see a bug - mailing is easy.
Issue tracker might be (and I think is) better for a developer working in the project, but for a wider audience it would be harder to present and explain how to use it, especially taking into account wide variety and differences between different issue tracking systems.
One project can use Bugzilla, another will stick with JIRA, third with... GNATS, etc etc, etc. There's just no way to present all this "zoo" in a way that would be as standard and uniform as
Report bugs to: mailing-address
Note above doesn't mean that projects shouldn't be using issue tracker internally. As explained in an excellent answer to related question,
Your bug tracker is for your convenience, not your customers'. If you can't be bothered to take their phone or email issue and enter it yourself, how do you think they feel?
You need to be able to enter issues and assign them manually to a client...
Best Answer
Store a clear-text 'digest' of each email address alongside the hashed actual email. The digest should contain enough information to bring the number of candidates down to a reasonable handful (I'd say a factor of 1000 or more isn't unrealistic), but not enough to guess the entire email address. For example, you could use the first two characters from the user part of the address, two characters from the domain name, and the TLD part; this would turn 'john.doe@example.org' into 'jo@ex.org'.
Finding collisions now becomes a two-step process: first, find all entries with matching digests, then do the actual hash comparison only on those. Instead of downloading all hashes from the DB for each check, you pre-filter them down to about 1/1000. That is a significant improvement, and while you trade some security for it, it's better than either alternative.