When you delete files, it goes from Your Files to the Recycle Bin, obviously. You know that part. But when you delete the files in your Recycle Bin, they don't disappear; instead, they are 'sent' to the $Recycle.Bin Folder. Quoting wiki:
You cannot delete the $Recycle.Bin Folder; it is built in and will always reappear when you delete it.
To see the files hidden in the $Recycle.Bin, you just do the process you described earlier, except that it's 'show hidden files and folders', rather than just 'folders'.
To your additional tidbit of information, your computer is just slow; mine does the same although not as frequently now. Usually, when you wait or restart the deletion process, Vista will finally total up the amount of files and the size being deleted and then starts the deletion process. This is what you see when it's actively deleting, but the number of files it says are deleting increases as it continues. It usually only happens when you are deleting a large amount of files. When I upgraded my RAM, I got less of this problem.
