You likely should make your legacy app UAC aware (e.g. Microsoft instruction for application developers on Vista, a Code Project tutorial) and request special privileges for it, to continue to use HKLM or equivalent. Once your program has the proper privileges (e.g. administrator) it should be able to continue functioning in the UAC environment as it did in legacy Windows.
One side effect is a non-administrator would not be able to properly install your program, but this is not unusual in the "new world" of Window Vista, 7, and everything going forward. It looks like the "everybody is an administrator" philosophy is not coming back.
(Note: I use the term "administrator privilege" but mean whatever is the least privilege you will need to get the job done).
Likely it will require a bit of work, when I see caveats like this in quotes:
Elevation procedures surrounding
installers are a bit too complex to go
into detail here, however be warned
that the requiresAdministrator flag on
an MSI package does not actually
provide full administrator
permissions. This actually behaves
slightly differently and runs as a
subset of the full privileges unless
you use a bootstrapper to gain full
elevation. It is rare that installers
would require these additional tokens
as the installer's administrator
permissions are generally sufficient.
The benefit is once you've converted one app, you will have the knowledge and code base to upgrade other programs accordingly.
I'm sure other people will suggest code workarounds which are satisfactory and likely won't use HKLM.