Wouldn't it just take 1 person doing the verification on a new message to catch this though?
That being said it's possible for all of Bob's contacts to have been MITM but not all of Carol's so each person does have to check at least one conversation to be sure.