Say I have a site that has a user registration process where, when a user enters an email address already in use, an error message is displayed telling them that. This seems like a easy way to a malicious user to enumerate users.
Would adding CAPTCHA to the registration process be enough to prevent user enumeration?
Yes! In order for user enumeration in an account registration form to be at all useful an attacker will have to make thousands of automated guesses. This vulnerability is not about informative error messages, in fact even if you remove the error message you still cannot let two users occupy the same username. By this general failure alone an attacker can determine that a username is in use.
