Does the performance change based on your recycle bin being empty or full? Even at 1%, if you have a 500 GB drive that is still 5 gigabytes of files in your recycle bin, which can be a lot of files if they are typically pretty small files.
I find it works a lot better to remove files from the recycle bin based on how long they have been there, not size.
Anti-virus is another possibility. I have also seen other 3rd party tools that install themselves in place of the recycle bin. Check for that as well and try disabling them. If nothing else you could just start disabling all those applications running down in your system tray and see if that makes a difference.
If none of that works then get Process Explorer from SysInternals and see if you can tell what is going on when you delete.