Please tell us whether you also cleared the System Restore Points and Shadow Copies when you did the Disk Cleanup and removed unneeded programs.
I’ve noticed the same gradual loss of free space on my Vista machine and could often regain many gigabytes by clearing these automatically generated files.
The option to clear these files seems to be available only if you chose to run Disk Cleanup for all users of the computer instead of for only your own files.
Restore Points and Shadow Copies are valuable, so you may want to keep them, but they do build up in size.