Is that really a problem though? Most people would just add their friends via username and bypass the whole user discovery process. Discord has demonstrated that this works perfectly fine, even with anonymous accounts not tied to emails.