Hmmm, there is one other thing that can some times happen.
When you try and save a replay and it doesn't save properly you can be left with a labeled file that's 0 kb. I had a few of them on my old computer and never was able to delete them.
Try going to the replay folder and deleting everything in there, if you can't then you can delete everything except those files and the Toribash folder.
They're nothing more than a minor inconvenience so there's no need to worry.