It's very strange; I think I have a spook in my PC. Sometimes when I delete files, the Recycle Bin doesn't show any files there; I don't Shift+Delete any files. Also, sometimes the files appear on their own after some time. To boot it all, my hard drive space is getting eaten up mysteriously on my portable hard drive. What is happening? Do I need to reinstall my Recycle Bin?
This is the funniest problem I've heard of recently. No, you do not have to reinstall anything (you cannot reinstall the Recycle Bin without reinstalling Windows itself), nor do you have a ghost in the machine; you are just not being attentive enough. And yes, this is not a Windows issue, so no need to blame poor old Windows for this; this is a human error.
When you delete files, they do not actually get deleted but get marked for deletion; the files are pretty much still there in the storage device. Only when the Recycle Bin is cleared, do they get deleted. This is true only if you don't unplug your device before deletion. You've unplugged the device before hitting 'Empty Recycle Bin,' causing the mysterious disappearance of the files from the Recycle Bin and their subsequent appearance.
This also explains the mystery of your hard drive space being eaten up -- all of the "marked for deletion" files are still present in the device you are using. If the deleted files aren't showing up at all in the Recycle Bin even after plugging in the device, here's what you need to do.
All you need to do is investigate the device a bit by unhiding files in Windows.

1. Go to My Computer, Tools | Folder Options.

2. Scroll down to Show hidden files and folders and tick it OFF. All hidden files will show up.

3. Now go to your portable device and note all the hidden the folders there. Recognise anything? Delete all hidden folder/files that you know you had deleted before.
4. Empty the Recycle Bin. Now your space should also have "mysteriously" come back.