The issue is in your backend code, specifically it is not correctly determining that the app has been installed by the shop. I can offer a few suggestions on where to look but without more details on how your backend code is set up they’ll be limited in usefulness.
No server record of installation
Does your backend create a record of the shop that installed the app in your OAuth callback handler? If not, you’ll need to add this otherwise your backend won’t know if it’s been installed in the shop it’s being loaded in. If you do have this already, then you likely have a bug in the code that checks if the shop loading your app has installed it.
Incorrectly decoding the session token
You should use the Shopify API for your language to decode the session token when making requests from your embedded app to your backend. If you do this yourself you’re likely to introduce bugs that might result in your backend thinking the app isn’t installed.
These are the two most likely explanations for what you’re seeing based on my experience and the few details I can glean about your backend implementation.