This happens to be a lot, and in all Windows 98, Windows NT 4.0 and sometimes W2K. Though I run Litestep, so I don't tend to pay that much attention to the Recycle bin, so I've set the bin limit to something tiny so that files keep getting deleted fairly often.
The only remedy that I've found for this problem is to reboot the machine, then whatever was causing the problem doesn't seem to anymore and you can recycle to your hearts content. Sometimes I've actually found that the desktop icon for the recycle bin says that I've got stuff in there, but I actually don't..it's a little lost..Regards