StoneRings I tried to replicate your issue.
$ pm uninstall --user 0 com.android.vending
Success
Restarted App Store, Play Store was listed as uninstalled, succesfully reinstalled it through App Store.
Maybe with -k: keep the data and cache directories around after package removal?
$ pm uninstall -k --user 0 com.android.vending
Success
Restarted App Store, Play Store was listed as uninstalled, succesfully reinstalled it through App Store.
No problems here.
I think you need to read the reply by other8026 O you did... well, anyway, let's try:
$ pm uninstall --user 0 com.android.vending
Success
$ pm uninstall --user 0 app.grapheneos.gmscompat
Success
$ pm uninstall --user 0 app.grapheneos.gmscompat.config
Success
Restarted App Store, Play Store is gone! Just as Play Services.
$ pm install-existing --user 0 app.grapheneos.gmscompat
Package app.grapheneos.gmscompat installed for user: 0
$ pm install-existing --user 0 app.grapheneos.gmscompat.config
Package app.grapheneos.gmscompat.config installed for user: 0
(These work here because, unlike Play Store, these are system apps and their installers remain on the system partition after uninstalling them.)
Restarted App Store, Play Store is back, just as Play Services, and can be succesfully reinstalled.
So try running:
pm install-existing --user 0 app.grapheneos.gmscompat
pm install-existing --user 0 app.grapheneos.gmscompat.config
It should solve your issue.