As long as you're careful to limit yourself to only the exact Registry keys left by the program, you should be fine. They're not doing any harm, since the program that used them is gone.
Note that
HKEY_CURRENT_USER (HKCU) is just a "link" to one of the entries under HKEY_USERS_S-1-5-21... etc. It's there so programs (and you) can just work on the Registry bits that refer to the current user, and not need to figure out which of the longer entries is the current user. If you delete an entry from HKCU, it's deleted in that user's HKEY_USERS_S... area too, so don't be surprised if you can't find some entries in the one place after you start deleting them from the other place.