You're right, it's probably the easiest way to permanently remove the ability to save the history of the recent open/save dialogs for programs that implement it. All that Ccleaner does is remove the values of those keys, not delete the keys themselves, so you would have to run in every time you wanted to clear them rather than them not being stored there at all, like you're currently implementing.
LastVisitedPidlMRULegacy is supposed to store values of the location of the last executable used in the open/save dialog, just like LastVisitedPidlMRU. However, given that you are that much into your registry, it seems you are in more of a position to tell us how it is being used on your system than we can. What values does it contain? Are they the same as the LastVisitedPidlMRU key? What does it store? Does it act in the same way and save values as the LastVisitedPidlMRU key?
To directly answer your questions:

Quote: Originally Posted by
windough
1) Is it advisable to also delete that third "...Legacy" key as well, and if not, why not?
2) What is the function of that third "...Legacy" key?
3) What would removing it do, or not do?
1) It is rarely to never advisable to delete any registry key of a Windows operating system, with the definition of advisable meaning someone on here would recommend that you delete a key for the betterment of the OS. In terms of being advisable to achieve a certain goal that is not the intention of the OS or officially supported by it, that is a different story.
2) The function of the third key is as I explained above.
3) Removing it would most likely have much the same effect as removing the others. However, you are in more of a position to tell us what it would do to your system. It should be very simple to test, given you have already been in there and deleted other keys, so you know how to go about it.