slowly running out of ideas too...
when searching this forum for Unable to resolve host "apps.grapheneos.org" one gets a lot of generic hits, often in combination with missing networking permissions of an app. It is reproducible on-the-fly by just removing the Appstore's networking permission, then trying to refresh or install an app.
A couple of things which came to mind:
during testing: disable VPN or firewall software or Ad-blocker etc. (VPN has been excluded so far)
I still miss some information. You confirmed that the gmscompatconfig app is there but we're actually
looking for 3 related Apps (at least on my phone):
Apps -> All apps: show system, then search for "gms"
- gmscompat
- gmscompatconfig
- gmscompatLibrary (0 byte)
I don't think force stopping or cleaning cache/data would make a difference, probably won't hurt...just make sure they are not disabled where it can be done. Or disable them and try installation again, who knows.
Not sure we've searched for Google play store/services in the list of apps: "Google Play"
it should not show either Google play services or store
if it does, uninstall it here if possible, see if installation runs through now
Maybe resetting the Appstore could help.
The aforementioned private space installation might be a good idea.
Other than that, at this point I personally would try what has been said in
https://discuss.grapheneos.org/d/24872-how-to-reinstall-google-play-store-after-it-was-uninstalled-via-adb/24
Maybe there are some videos online to give you an idea how to use adb and just remember not to issue
commands until you understand what they do (show/list/read are normally ok)