I why not actually always send an email to that address? If the email isn't registered, change the message to suggest that perhaps they signed up with a different email, or they'd like to sign up instead?