Alice sends a message to Bob, her device asks the messaging service for Bob's account's identify and public keys.
This is a classic trusted third party problem. We need to trust the service that the public key provided (and stored in the blockchain) actually belongs to Bob.
This boils down to Zooko's triangle: if the service allows to associate the account with a new key, there is no way to prove the new key actually belongs to Bob. If there is no such way, Alice will have to somehow figure out the undecipherable new ID of Bob.
The only benefit I can see of backing the keys in a blockchain is that your own client can monitor the blockchain for new keys associated with your account, ringing alarm bells in such a case.
It depends on what you are establishing trust to, Bob's account, Bob's first key or Bob as a person? The service could write a hash of Bob's account name / phone number / whatever and the account's identity to the chain. That way it cannot easily respond with a different set of keys for the same account.
One attack vector I can think of in terms of a malicious third-party is that they could take your initial account creation request and key, create their own key and use that as the initial one of your account in the chain.
In this model you have the ability to find out about that though.
This is a classic trusted third party problem. We need to trust the service that the public key provided (and stored in the blockchain) actually belongs to Bob.
This boils down to Zooko's triangle: if the service allows to associate the account with a new key, there is no way to prove the new key actually belongs to Bob. If there is no such way, Alice will have to somehow figure out the undecipherable new ID of Bob.
The only benefit I can see of backing the keys in a blockchain is that your own client can monitor the blockchain for new keys associated with your account, ringing alarm bells in such a case.