This topic moved so quickly I didn't notice it earlier. Here is my take: The question of deletion falls into two parts.
Part A: Defining what you want to delete - will greatly benefit from the presence of indexes.
Part B: Deleting what you have defined - will be slowed down by the need to maintain the indexes as well as the associated records.
There is only ONE WAY (and this has been discussed before) to quickly get rid of a lot of data from temp tables. That is to delete the whole table at once. Which of course leads to bloat very quickly. Which you then avoid by putting the temp tables in separate files that you map, use, unmap, and delete (the WHOLE FILE). That's as fast as it gets when dealing with huge amounts of data. OR you never use a temp table at all - you just map to the original source.
If you are using indexes to be selective AND you are not deleting everything when you are done, then you cannot delete your temp tables. BUT you could do something to mark them so that subsequent operations ignore the deleted records. Because there is a third strategy. Add a field to the temp table that says "MarkedForDelete" (or pick a shorter name like "Used"). Then in subsequent queries, add the criteria "AND (Used=False)" so you don't re-use a used record. But DON'T DELETE IT! Just leave it around until you are ready to do a bulk operation that will erase the whole thing.
Stated another way - if this IS just a temp table, DON'T delete ANYTHING a little bit at a time. Just mark stuff as unusable and then, when you are done, get rid of the WHOLE THING AT ONCE. Why delete in retail when you eventually plan to delete wholesale?