Remove "User already exists" message on registration, instead just display the message that further instruction is sent via email. Maybe send an actual email with account recovery link, but then protect the form with captcha to avoid spamming mailboxes.