The problem with that, is that you fail to take into account that for all intents and purposes, the registry is simply a database. It's a very simple, very crude, and very ugly, flat file database. I'm sure it was only intended to be a temporary solution, and like so many temporary solutions, ended up being extended well beyond its original scope and intent. Unfortunately, now we're all stuck with this rather ugly and ineffective solution.
Flat file databases do have a couple of small things going for them however. One, is that they are very easy to construct. Someone with only a minimal knowledge of programming can make these things. They're also generally very fast on account of their low overhead. As they get bigger, it does get a bit harder to search them, BUT much of that is negated by the entire thing being loaded into RAM. Part of being essentially a specially formatted plain text file, is that you can cram a huge amount of info into a very tiny amount of space. While the registry has certainly ballooned beyond what it was when it took center stage in Windows95 (it existed at least as early as Windows 3.1, it just was almost never used) the amount of RAM in computer systems has more than kept pace.
I'd be surprised if the registry on the average computer was over 64MB. Which, granted, is a lot of text, but when we're talking systems with 4-8GB of RAM being pretty standard, it's nothing. And if the entire thing is loaded into RAM, you can search through every single entry in a minute or two. But you generally don't have to do that, because if you look a little closer at the registry the designers clearly anticipated this. There's a path system that programs can use to quickly locate the bit of info they need. It's one of the few good things you can say about the design of the registry, though why you want to store that much sensitive info into a single location, providing an excellent single point of failure... Well, only Microsoft can answer that one. I much preferred the old DOS system, where every program was it's own self-contained ecosystem. I rather like the way Apple puts kind of a modern spin on this. Under the hood, every .app file on OS X is really a directory tree for that app. You can probe it with the command line if so inclined. Everything the program needs to run is contained within, and the Finder shell automatically looks for the main executable in a specific location within that directory tree. Installing an app is as easy as dragging the icon to /Applications, and uninstalling is as easy as dragging it to the Trash. None of this wizard crap Microsoft has had a hard on for since Windows95.
But, long story short, it's a myth that leftover bits of programs in the registry have any non-negligible impact on system performance. It's simply not true. System performance really doesn't degrade over time, it's that our perceptions change. The expectation bar is raised as we become accustomed to our computer's performance levels, and as we are aware of faster computers being made. If you format, the process of reinstalling is usually slow slow and arduous, that by the time you're done, the system seems very quick and responsive. It's all in your head.