I've just run the free trial copy of Registry Mechanic, and I came up with 200+ problems. Some urgent, some medium, etc.

Is this scare-mongering to get sales, or is it a worthwhile purchase?

Rannoch

The first time you run a Registry cleaner several hundred listings will be found.

Every program ever installed or uninstalled has changed the registry.

Most uninstalls just leave the registry with their remains.

As to paid programs I suggest RegSupreme over Registry Mechanic.

http://www.jv16.org/

Cheaper & better. You can get the whole JV16 PowerTools suite for the same price as Registry Mechanic.

If you just want a freeware cleaner this is good: (just not as powerful as JV16).
http://www.hoverdesk.net/freeware.htm