This is a fact. Many of the Application Compatibility Updates you get from Microsoft are to fix damage to critical OS registry keys. There is simply no way for a registry cleaner to know for certain whether a key is still in use or not. It therefore has to make an educated guess. A well written cleaner will avoid mistakes, but a poorly written one will delete many important keys.
Since registry cleaners often try to beat their competition by increasing the count of keys deleted, many tend is to be overly aggressive when deleting keys.
Unreleased third-party benchmarks using RegBench have shown that popular registry cleaners ran on a typical real-world PC do not boost registry performance one bit. Only rebuilding the hives from scratch (described elsewhere on this page) boosts performance. This is in line with theoretical predictions. Your registry has hundreds of thousands of keys. Your registry is loaded into virtual memory in an optimal data structure allowing for very quick traversal (searches). Deleting a few hundred (or even thousand) keys isn’t going to make it perform faster. Some people suggest that utilities that correct keys with errorneous values may speed the system, if those errorneous values were slowing it down. However, we consider these the ‘registry repair’ genre instead of ‘registy cleaner’.
The best theoretical way to boost registry performance is NOT by deleting keys, but instead by rebuilding the registry hives from scratch and/or defragmenting the backing hive files (in the case of HDDs). HOWEVER, defragmentation of the backing hives on the HDD is now redundant in NT 6 (Vista) and above, as the OS does it for you. There are many freeware utilities to hive rebuilding (e.g. NTRegOpt), but be careful with them as some are incompatible with Vista+ and may result in an unbootable system. Before use, make a backup of your registry hive files and be sure you know how to restore them in the event they are corrupted. It is also important to remember that any gains to registry performance are likely to very marginal, and probably nothing you do to the registry will substantially increase overall system performance.
For more information about Registry Cleaners in general, see the Wikipedia article on the subject.