This is a bigger question then it might seem. I'll try an focus on the privacy aspect, rather then the engineering aspect.
This scenario isn't entirely implausible, given the Ashley Madison leaks, and the repercussions individuals and/or companies received.
The core issues here are:
- How do I provide a secure experience, without some semi-unique publicly identifiable information?
- Can I offer users some level of plausible deniability?
- In the very likely scenario of password recovery, how do I handle this with some level of privacy?
For the purposes of this question, I will continue with the understanding that we are:
- Attempting to mitigate casual or widespread "outing"
- Preventing the linking of user information to a real human being
The difficult part is that an account by nature usually needs to be unique, and tied to someone. Additionally, it needs to be secured with something like a password to keep conversations private ("something you know").
To add some additional protection, allow only those WITH an account to query for other users. All services and functionality are hidden behind a login screen. How you decide to implement registration is a separate issue. This idea is implemented on several services already, but it is unclear how effective it is. You would also have to avoid listing account creation date/time anywhere. This satisfies points 2 and 3, without dealing with 1.
Easiest thing would be to force a user not to use a public email service or phone number. Again, how this is implemented is a software engineering question. You will have to deal with bots or users who wish to abuse the platform. This satisfies points 1 and 3, unlikely 2 as well.
Taking an idea from how apps/users work in censorship central China, assign each user a "random" ID. These could be 8-12 digits long so they are both unique enough but also rememberable. Having a copy of this ID anywhere besides the user's brain and the database can enable linking the two, defeating any privacy gained. This means no emails, no phone calls, no "selfies", or anything of the sorts. Users can assign themselves a public facing name when changed by the user at any time, points to a generic "doesn't exist" page.
To gain some level of plausible deniability, you can have a "no sign up" process. Users could have multiple accounts tied to an email address or phone number without a verification process in place. Each time someone wishes to "register", a random ID is assigned and only displayed once. From there on to access that account, you provide the "secret" ID and a password. The system will let you register a set number of accounts per an email address or phone number, but more than the usual 1 to 1 mapping. These last two paragraphs satisfy points 1 and 2, but not 3.