RECYCLE BIN SOLUTION
DO NOT RESTART FROM SCRATCH
If you are in Windows XP (might be the same with 98, not sure though) go to C:\RECYCLER or in Vista go to C:\$Recycle.Bin and there should be a folder in there that represents your recycle bin, in XP it is named a long series of numbers in vista it is shown as being named recycle bin but is actually a long number folder as well, if you cannot see these folders then un-tick "Hide protected operating system files" and tick "Show hidden files and folders" in Folder Options.
My recycle bin disappeared from my desktop a while ago and I could still find it.