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
System/Network Administrator
SmarterTools Inc.
(877) 357-6278
www.smartertools.com