Как повысить скорость удаления?
Измените немного архитектуру таблиц и логику обработки данных.
Добавьте в таблицу ещё одно поле - флаг, сигнализирующий, что поле удалено. То-есть, при удалении, Вы будете делать UPDATE, а не DELETE.
В моменты минимальной нагрузки, уже можно будет произвести DELETE отмеченных строк.
Пакетно.