This would be normal if the files were on a Network Share of any kind.
The Recycled folder itself can become damaged. Files are moved to the folder and the Recycle Bin on the desktop appears full but you cannot view the contents and the Empty The Recycle Bin command may be unavailable, or simply doesn't work.
Deleting the Recycle Bin and then restarting Windows, which will re-create and restore its functionality. Restart the computer and delete the recycle bin by pressing F8 at the WinXP Startup menu, and then select Safe Mode with Command Prompt. Navigate to the correct drive prompt (ie C or D). Type the following commands, pressing Enter after each line:
attrib -s -h recycler
del recycler
How the Recycle Bin Stores Files (Q136517)
Microsoft Knowledge Base Article - Q173416
Cannot Empty Recycle Bin or Modify Recycle Bin Properties
Microsoft Knowledge Base Article - Q246726
Cannot Delete Any Files in Windows
Any error should be recorded in the Event Viewer as an "Application Popup" in the System Folder. You can use the View/ Filter and retrieve the message.
You always have System Restore to try.