https://dev.mysql.com/doc/refman/8.0/en/innodb-loc...
1. Начать транзакцию.
2. Выбрать ключ запросом SELECT ... LIMIT 1 FOR UPDATE SKIP LOCKED
3. Удалить эту строку либо пометить ключ использованным.
4. Применить транзакцию.
В этом случае ключ не попадёт дважды, так как строка при выборке заблочится и больше не попадёт никому другому, пока транзакция не завершится.
Движок таблицы должен быть InnoDB, т.к. только он в MySQL умеет блокировать построчно. Если всё же нужно работать с MyISAM - то тогда на первом шаге блокировать всю таблицу через LOCK TABLES, на последнем - разблокировать, но в таком случае одновременно только один экземпляр скрипта сможет пользоваться таблицей, другие будут ждать в очереди. Либо самописные оптимистические блокировки использовать.