What Gwyvian said is one aspect. When you install something, and deinstall it again, this will not delete all files. Some data are kept, like registry entries and more control data. But this will not account for the weirdness you spoke of in the post prior to the one I quoted. Also, as she said, you get temp files but that shouldn't be so many if we are talking installed software here.
A real uninstaller will help here, best if followed by a defragmentation. When you store data, you store them where enough space is found. So if you store a file and delete it, you can only store new files there if they are <= the deleted file. Otherwise they don't fit in the gap. Defragmentation will remove such gaps and get you more usable free space (100MB space aren't worth much if they are scattered over the HDD in form of 100KB small gaps).
More issues are swapping. That is, when you run multiple programs at once, program state is kept in memory. But when your memory is full, or when you switch to another program, this state is temporarily stored on the HDD and read back in when you need it again. The more multitasking, the more swapping. You don't keep data for more than one program in memory at one time. So this is a reason for why you need free space on your HDD.
Anyway, what you described is strange and I can't come up with an explanation. If you really want one, I fear you will need to explain in detail what you did (how you deleted etc.) and it would be tedious. 
Anyway, my advice: get a bigger HDD. 700GB really isn't enough for a gamer. If you have a desktop machine, just plug in more HDDs. If you can, even get an SSD for Windows and store programs and other files on regular HDDs.
Oh, and get more RAM.
More memory is always good. Will also need less swapping, so your programs run faster because it doesn't constantly need to write to/read from disk. Disk operations are terribly expensive.