without knowing anything, i am going to guess that they could either directly import the same code that the windows api uses (either via knowing where the implementation code resides and load that), or even statically link the library! After all, regedit doesn't need to obey cleanliness rules that other non-first-party programs would need to - presumably, because if those registry editing api/format changes, regedit would get updated along with it!
This might have changed at some point. I was curious about the latter part of your question on how it made changes without the Windows API (I assumed it used an older DOS API), but my `regedit.exe` _does_ have the `This program cannot be run in DOS mode.` DOS stub in it.