People often forget usernames but not so often e-mails. The e-mail is usually the primary/only means of identifying users anyway so you're not going to provide it back on request anyway.
ie <email prefix>+<tag>@gmail.com
That tag could be anything or everything.
One of those uses multiple domains (it's an iCloud account that I registered way back in the iTools days, so it supports @mac.com, @me.com, and @icloud.com....possibly even @itools.com, not sure about that one).
I regularly use a + extension to the addresses that support it when I'm signing up somewhere that I don't 100% trust, and that allows arbitrary additions to the address. And I don't always remember what version of a site's name I will have used (eg, user+hn@example.com, user+hackernews@example.com, user+ycombinator@example.com, etc).
I recognize that I'm an outlier, but trial and error is completely infeasible in this scenario.