The time it takes to find a registry value does indeed increase as the hive grows, a basic characteristic of hierarchical databases. When SONAR requests a registry value, specifying the path does
not mean Windows can instantly zero in on the key's physical location in the file. Every search involves scanning, entry by entry, until a match is found. I do a lot of benchmarking of this kind of thing, part of the process of optimizing my own code.
The scan, however, is pretty durn fast because the registry is cached. But it can still sometimes be a bottleneck. Remember, a program such as SONAR (and its hosted plugins and the Windows functions they call) will typically make dozens or even hundreds of registry queries in response to you just clicking one button. More involved processes such as program initialization or a plugin scan will require literally thousands of registry queries. Even if each one takes 1 microsecond, they can cumulatively account for several seconds' execution time.
So registry reads and writes are relatively expensive, and get more expensive as the registry grows in size. Sounds like a good argument for a registry cleaner, right? But no. Registry cleaners remove such a small percentage of the total data in the registry that any minuscule speedup they might achieve would be irrelevant. Given that they're so prone to breaking something, the risk:benefit ratio just doesn't pencil out.
So the bottom line is: skip the registry cleaner.