You’re correct that if you use the system the way it used to work they can trivially build that connection, but (and I know this is a big assumption) if it does now work the way they say it does, they do not have the information to do that any more as the client doesn’t actually authenticate to the server to send a message. Yes, with some network tracing they could probably still work out that you’re the same client that did login to read messages, and that’s a certainly a concern. I would prefer to see a messaging app that uses cryptographic keys as the only identifiers, and uses different keys for different contact pairs, but given their general architecture it seems they’ve tried to deal with the issue.
Assuming that you want to use a publicly accessible messaging app, do you have any ideas about how it should be architected? The biggest issue I see is that the client runs on your phone, and unless you’ve compiled it yourself, you can’t know what it’s actually doing.
I agree that them having users’ phone numbers isn’t ideal. There are other identifiers they could use that would work just as well. However, both the client and server are open source, so you can build, at least the client, yourself. If you can content yourself that it does not leak your ID when sending messages, then you don’t need to trust the server as it does not have the information to build a graph of your contacts. Sealed sender seems to have been announced in 2018, so it’s had time to be tested.
Don’t get me wrong, the fact they require a phone number at all is a huge concern, and the reason I don’t really use it much, but the concern you initially stated was addressed years ago and you can build the client yourself to validate that.