The biggest thing is the file system. Unfortunately, no matter how much you defrag, there are files that will not and can not be organised correctly. As a result, as the computer gets used more and more these files (like the registry, critical system files) grow larger and more fragmented, which leads to reduced performance.
Invalid registry keys are also a big performance problem. Although you've mentioned you cleaned the registry on a regular basis, you have no way to know that what you're doing is actually getting rid of all the invalid keys - unless you want to search through the registry by hand, you're relying on what the author of the tool deems to be invalid.
(That said, registry cleaners like CCleaner are awesome, even if they might miss stuff that I might remove)
Also, the file system can suffer corruption issues over time to - typically people do a format of some description when they reinstall, which replaces the file system, and typically any corruption that goes along with it.
Unfortunately, Windows is like a giant filing cabinet. You can do your best to keep it clean and organized, but eventually you're going to just have to rip your files out and start all over again.
Edit: Molly pointed out some fantastic tools in the comments that may help in defragmenting large system files that aren't normally defraggable (is that even a word) by a normal defrag tool. These tools if used properly, could help in prolonging that reformat.