The solution to this is to have multiple independent clients all working with the same protocol. This way it doesn't matter if an IM service handles your public keys, cause if they send different ones, they can't prevent the client from notifying. They simply don't control the client.

In general, it is the control of FB over the whatsapp client where the vulnerabilities lie.