Recently I got into UEFI (TianoCore) development. One of UEFI's properties is that a part of it survives the OS load and remains resident to provide a limited set of firmware services to the OS.

Its predecessor, PCBIOS, provided software interrupt services that ran in real-mode - with the effect that every operating system since about 1994 had to switch back to that mode if it wanted to make use of these services. Most didn't, so they simply ignored them and implemented those features by themselves, which was usually faster and more robust, too.
Instead of learning the lesson that nobody wants or needs firmware runtime services, UEFI Runtime Services were adapted to that new world: they're regular entry points into protected/long mode code.

But these modes allow, or even require, page tables that can change the address under which code or data is found. How could the surviving UEFI code deal with that, not even knowing at which address itself is residing once the OS messed a bit with the memory map?

UEFI doesn't walk the current page table. It also doesn't provide a way to convert from logical to physical addresses and back. Instead, the OS can send a partial memory map to UEFI once (and only once!) that must cover all memory regions UEFI claimed as its own (and only those regions!).

This must happen before the new memory map is enabled, and UEFI triggers handlers that registered themselves for that event. In these handlers (and only then!) can code request address translations so it can fix up its data structures. Afterwards UEFI patches up all relocations to match the new memory map and returns. From then on, UEFI code can do no further address translation.

The expectation is that the OS switches to a page table matching that memory map before next calling into UEFI (or the addresses would be all wrong), and that the UEFI addresses never change again since all later requests to update the memory map will be refused with an error code.