How about you do away with user-selected usernames for I&A altogether? Use the e-mail address, or some system-generated ID. Then you could do this for the registration process:
1. Prompt user for basic identifiers. Maybe even ONLY the e-mail address.
2. After user submits form for #1, respond with "an e-mail has been sent with further instructions to continue the registration process" regardless of whether the user exists or not.
3. New user receives e-mail, clicks link, finishes registration.