Thanks for everyone's assistance. Considering the conditions required to reproduce this, I'm not too worried about about it...I'll just try to remember to avoid using delete when getting rid of...

The database has automatic statistic ON

I ran a few more tests, this time on a table with 100,000 rows. The slow behaviour only seems to manifest itself if I delete...