For quite a while now, I've tolerated this issue on both a Windows 2000 Professional and an XP machine...whenever I select and 'delete' files, it can take up to two minutes to complete the action. Those machines weren't always like that, but over time the delete process just seemed to slow way down.
Worse, the whole system is pretty well locked up while we wait for the files to go away.
Brian Cryer has a neat little article with an obvious solution...empty your damn Recycle Bin once or twice a year! It worked for me...I only had about 1.2GB of crap in there...go figure. Thanks Brian (for pointing out what probably should have been obvious)!