If the user chooses to uninstall your program, what do you do with the data your program kept in HKEY_CURRENT_USER, and other parts of the user profile? Should you enumerate all the profiles on the machine and clean them up?

No. Let the data go.

First, messing with the profiles of users that aren't logged on can result in data corruption, as we saw when we looked at roaming user profiles. Users don't like it when their data get corrupted.

Second, the users might want to keep that local data, especially if they are uninstalling your program only temporarily. For example, maybe your program's installation got corrupted and the user is doing an uninstall/reinstall in an attempt to repair it. Or the user might be uninstalling your program only because they're going to be reinstalling a newer version of your program. If you deleted all the users' saved games, say, they are going to be kind of miffed that they won't be able to finish off the big boss that they've been working weeks to defeat.

Now, if you want, you can clean up the per-user data for the current user (after asking for permission), but you definitely should not be messing with the profiles of other users.

(Remember, this is my personal recommendation, not an official recommendation of Microsoft Corporation. I know that had I not included this explicit disclaimer, somebody would have written an article somewhere saying that "Microsoft says to...")