The indexing helps as long as you are still only deleting small batches, if you have a rewrite of the stored procedure you could easily send me that would save me some time in rewriting it myself (although it's not a particularly complicated proc).