This is not a behavior we've seen, or had reported, so I wanted to offer a theory. Something I could see causing a performance decrease when deleting lots of data is disk speed. Can I have you run the disk queue counters as detailed here at the link below and let me know what you see for average queue?
Kyle Kerst
IT Coordinator
SmarterTools Inc.
www.smartertools.com