Side channels are the only way, practically speaking. Call them and have them read off the hash of their key and verify it against the key you received from "them". Or have them send a nonce value through the system to you that you provided over a side channel.

Any time you have a central authority providing that validation, you have to trust that your "friend" hasn't fooled them.