Are you sure you don't have "Don't show items that would be automatically re-created" option enabled in the Registry Cleaner?
The jv16 PowerTools 2005's registry cleaner contains a feature called "MRU Scan" (you can enable/disable this from the scan options). It's a generic MRU cleaner, i.e. it doesn't just remove non-working file paths but automatically detects MRU items and removes them.
The History/MRU cleaner on the other hand is a non-generic tool, it contains a pre-defined list of applications and information what kind of data they add to the registry.
In other words, the Registry Cleaner does analyze MRU items if you don't disable it. The jv16 PT 1.4.1's Registry Cleaner didn't have an MRU scanning feature at all. (Of course, it did detect MRU items with invalid file paths).