This is a tricky issue, for the exact reasons you mention: already taken usernames will cause an inadvertent verification of its existence, as can password reminders that use e-mail addresses as input. The latter can be handled by giving an ambiguous response, which comes with a slight (but negligible) cost of annoyance for forgetful users. The only method that comes to mind for avoiding username mining is forcing the user to pick from a fixed number of available usernames based on f.e. a part of the supplied e-mail address. This is a bit of "userland villainry", though.