As with race conditions, making things faster doesn't change things but only exposes preexisting problems. The preexisting problem I see here is sloppy definition of existence for the message: if you can see the message on a burning piece of paper, it should be considered to still exist (just as a message being sent with smoke signals does not disappear the moment it's committed to smoke).

E: The obvious way to fix this is to stop talking about messages existing/not existing, but talk in terms of messages being stored in X (or having been deleted from X), for some value of X.