Did you, in fact, run into any serious problems with those deletes? (I now have a range of key space that I seem to have "damaged": if I do a LIST with prefix "requests_/" I now deterministically get an InternalError.)
Seriously, though, this new multi-delete is EPIC ;P. I am now deleting objects at an rate of over 4 million per minute! (Although, as these are POSTs, I wonder if these now cost me money; that said, it likely isn't going to much.)
(This is fast enough that I'm now "cleaning house" much more thoroughly than before: going through some of those "database buckets" I have and deleting obsolete indexes.)