OK, I had this problem, and I fixed it.

Background, and causes:
A Windows update a while back caused my main user profile to become corrupt. Therefore, I logged on as a different user, backed up my main profile (by manually copying the folder to another drive), and then proceeded to search for the corrupt file (which actually revealed itself during the copy).
When I removed this file, I was able to log on normally, so I deleted the back-up. This created a situation where a corrupt file, and several files I didn't "own" or have permissions to delete were now in the recycle bin. However, they didn't show up in the recycle bin!

Here's how fixed it.
1. Right-click "My Computer" and select "Explore.
2. Make hidden and system files visible. Tools>Folder Options..."View" tab, then hit the "Show hidden files and folders" radio button, and uncheck "Hide protected Operating System files." While we're here, you can also uncheck "hide extensions for known file types" because I hate that "feature." However, it's unrelated to the task at hand.
3. Expand the C drive in the file tree, and look for a folder called "Recycler."
4. Select it to reveal its contents. You'll need to delete these files and folders inside "Recycler." You'll probably need a special tool to do this, because they likely have locking handles, and are very likely to be protected by at least one other measure. Try "Unlocker." Unlocker - Free software downloads and software reviews - CNET Download.com
5. After installing Unlocker, select all the files in this folder, then right-click one of them (you will almost certainly have to wait a few seconds for the right-click menu to show. Be patient, it will come up.)

6. Select "Unlocker" from the right-click menu, then if there are locking handles found, you'll see a list of processes to which these handles belong. There's a drop-down menu in the lower right, select "delete" here, and then click "Unlock all." If there are no locking handles found, you'll just need to select "Delete" from the drop-down and click "OK." You'll very likely be told that Unlocker can't delete these files now, but it will offer to do so at next boot. Accept that, then restart your computer!

Note: if you have more than one hard drive or partition, you will need to clear out all the Recycler folders. There's one in each partition/drive.

That should fix the problem. When the Windows comes back up after the reboot, try deleting a file and then emptying the recycle bin, just to be sure.

Hope that helps!

--Sean C.
Microsoft Certified Professional, Windows XP Pro