When using InnoDB backend database and the queue size becomes large (and high throughput) the delete and index rebuild start to become the limiting factor on the performance of the system.
This could be addressed with the use of a flag on the record and a mark and sweep approach.