Found a solution to this, it sounds like it is a issue/feature with Shopify App Bridge and it is related to
“Because the shopOrigin cookie is set during authentication, you’ll need to re-authenticate your app in your store’s admin” if you search that on the internet you get a bunch of results from different languages and systems all related to Shopify App Bridge
The solution is to access your app manually and having the shop-name as a single GET argument, like this
Hey, it’s been happening to me as I was trying install/uninstall and I have managed to understand why it may happen to some people:
If you uninstall the app while your code is not running, your app will not receive the app/uninstalled webhook and will not remove the shop tokens from the SESSION_STORAGE which is by default stored in a database.sqlite file. Then your app will detect your shop as already installed/registered (so no need to send you to the install screen) and will try to initialise the session with Shopify but Shopify will kill it because it’s using old tokens.
The simple solution is to get in the database.sqlite and remove your shop’s corresponding session, or just delete database.sqlite and restart your app.
This did not work for me, I cleared the session database locally and still got the same error, the only way to resolve it was to manually visit to Oauth URL of my app
For anyone with the same error, go to the live database connected to your code and remove the app credentials.
Then try to re-install. The matter would be resolved.