Registry Cleaning What and Why
I'm thinking. It may be useful to start a list of invalid registry entry types. Just did a Google search and didn't really come up with much.
DISCLAIMER-> I'm typing this from personal experience, so if I've got something incorrect, please point it out and explain why. Also feel free to add things I know I'm missing.
But for a learning experience and to calm some fears among the people who are unfamiliar with cleaner programs, it may be useful to have a list (obviously going to be very incomplete) of invalid entries, and what they did and why they are safe to remove.

First thing I can think of are shortcut entries. If a program has been moved or deleted, there still may be a shortcut entry pointing to its original position. These should be very safe to remove since shortcuts don't really affect any program, just a way to get to the program. In a pinch, there are other ways to get to a program and it will still work.

Temporary file entries. These can be created during installation, especially if the computer needs to reboot to complete installation. Once the process is finished, any link to the temporary file has now finished its work, but the installation may not go back and delete the entry. Links to temp files are safe to delete.

If you have removed a program, there may be leftovers in the registry. I have seen cleaners with a statement something to the effect of "if you know you no longer have the program...."
Entries that point to the old program itself are removable. If the entry says 'shared' I'm not sure its totally safe to make the decision on my own.

At times entries can be created that point to web sites, like for a flash or ActiveX file that displayed something when at that website. Safe to remove. If you ever go back to that site, the entry should be re-created, and if not, no sense in leaving it in the registry at all.

More difficult for the novice are entries that were left after an upgrade. Getting a newer version of a program may leave something from the old version that is no longer valid. For these, I have to trust that the cleaner is correct. Sometimes an update modifies the program, other times it replaces it. One example of replacement I can think of is Windows Media Player. I still have WMP6 on my system and can use it if I choose to, and the newest WMP is also there and functioning. Usually people don't want an old version cluttering things up but not necessarily.... I found an old Aida32 worked after I got a the "new" one and used both side by side to look for differences. Other programs like VirtualDub removed support for Microsoft's propriety in later versions, so I had to keep the old version 1.3c despite also keeping the newer and better features of the latest. Just mentioning these examples because a new version may or may not clean out old registry entries. It probably will replace what is needed, but if it has eliminated some "feature", then those entries may still exist. If you have gotten rid of the old version, the entries that a cleaner finds are safe to delete.

One site with some information »www.asmwsoft.com/products/regclean.htm that I got this information from-> OLE files (Object Linking and Embedding)- "Registry entries can become corrupted or simply invalid. This can come about after installing many different software packages which access the registry, or by installing newer versions of existing software. In the case of OLE applications, version information and OLE server id information can become invalid."