The mempool is just a temporary store of unconfirmed transactions. Each node's mempool is not synchronized, and in fact a node could choose to not keep a mempool at all. So no node needs to verify whether anyone else has a transaction, before deleting it from their memory. Miners will choose transactions from their mempool, to build new block templates that they will mine on.
What matters is the blockchain. Each new valid block will (likely) include some transactions, so when a node hears about that block, it will update its mempool accordingly (removing transactions that have been confirmed in the block).
Thus, miners can all be attempting to mine a block that includes the same (or different) transactions, and it is simply the first miner to find a valid block that will 'win', with their block being appended to the blockchain. All other miners will see this new block, and start to mine on top of it, adjusting their mempool (and thus the transactions they include in their new attempts to find a block) accordingly.