Regarding first point, for sure you should be using GUID of the page to store links and I don't think you should be afraid of additional query. If you choose the correct caching strategy in your code it will never be the case. For example, consider using output cache and data caching of the things returned by your repositories (have a look at Dancing Goat MVC implementation of CachingRepositoryDecorator.cs).
The second one, links in RTE. That's going to be more difficult. I'm not aware of any RTE module available that does it for you. Typically, we try to avoid using links directly in RTE and offer CTA and signpost widgets to editors and inside those widgets store page GUIDs and use those to generate links. But if you use links in RTE you would need to go back and change those links when you move the target page. Alternatively, after moving a page you can set up a 301 redirect in your configs and then you don't need to update RTE contents.