Here's an idea that's been floated many times in the past: Add e-mail as an alternative alongside phone numbers. Support in contacts in both Android and iOS. The only real difference these days is that one requires government ID (by law in an increasing number of countries) and one does not.

I fail to see any fundamental difficulty here.