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.