One option when uninstalling from the Programs and Features screen is to "Uninstall All" quicktime related files which they say is not recommended. Is that what I need to do?
That is what you had to do with Windows 95/98 -- uninstall EVERYTHING to do with QuickTime. Then reboot and install the older version. I don't know how it works in Windows 7, but since you'll be installing the older version back afterwards, I wouldn't worry too much. You can also make a restore point before uninstalling "Everything" to do with QuickTime.
Other than old games, there's nothing you need QuickTime for on a modern computer anyway. There are better programs to play movie files or do other non-game things that QuickTime used to be good for. It's even been recommended that you uninstall all versions of QuickTime due to security flaws, but that was under the assumption that you weren't playing games that needed it and could use VLC or Windows Media Player instead.
You can try ccleaner after uninstalling too, but it may be enough to do the thorough uninstall of QuickTime.