[tptacek]

You think you're making an argument against Signal, but you're in fact making the argument for it. The reason Signal deals in your phone number is precisely to keep them from managing databases of metadata about who's talking to who; the phone numbers keeps the social graph on the clientside.

Go look at RFC6121 Section 2 for one example of this. The point of Signal's design is that the server can't facilitate this kind of transaction, because it's unsafe for the server to keep that data in plaintext.