Now I'm thinking that Carol doesn't even have to trust Bob. As long as Carol has a kind 3 event from Alice that is old enough and Bob is in there, Carol can assume Bob is ok for signaling Alice's new key.
If Carol can get attestations from multiple people in Alice's old contact list that would be ideal.