Solve the issue in the most general way, where a message spec doesn't need to be aware of being deletable. We're checking messages in an order, which means we can build a set of deleted messages as we go. Then simply continue if a message was deleted by one of the already seen messages.
Depends on D14550