The first step in preventing username enumeration in an application is to identify all of the relevant attack surface. This includes not only the main login but also all of the more peripheral authentication functionality such as account registration, password change and account recovery. It is very common to encounter applications in which username enumeration is not possible in the main login function, but can be trivially performed elsewhere.
The second step is to ensure, in every piece of relevant functionality, that the application does not provide a means for an attacker to confirm the validity or otherwise of an arbitrarily chosen username. This is not just a matter of fixing obvious failure messages such as "username incorrect" vs. "password incorrect", but also of checking every aspect of the application's behaviour. For example, if the same literal on-screen failure message is generated by different code paths, then subtle differences may arise within the HTML source. Alternatively, the application may manifest timing differences when processing valid and invalid usernames, because different database queries and computational operations are performed when a valid username is supplied.
Of the various points of attack surface, account registration functionality can seem to be the most difficult area in which to eliminate username enumeration, If an existing username is chosen, surely the application must reject the registration attempt in some manner, enabling an attacker to infer which usernames have been registered? Using CAPTCHA controls and other hurdles may slow down the process, but they do not prevent it.
In fact, there are two ways in which an account registration function can be implemented which avoid introducing enumeration vulnerabilities:
The application can specify its own usernames. When an account applicant has supplied their required details and initial password, the application generates a unique username for them. Of course, to avoid a different type of vulnerability, the usernames generated should not be predictable.
The application can use email addresses as usernames. The first step of the registration process requires the applicant to supply their email address, to which a message is then sent. If the username is not yet registered, the message contains a one-time URL which can be used to complete the registration process. If the username is already registered, the message informs the user of this, and perhaps directs them towards the account recovery function. In either case, an attacker can only verify a username's status if they control the relevant email account.