How to detect that an app is linked to Play Store or not?
Go to https://play.google.com/store/account, with a regular desktop. Then click on the tab 'orders', you shall find there all the apps you downloaded via Google Play.

After clicking Install or Installed button, you'll get pop-up having device list. If app is already installed in a device with linked status, device would be inactive to send install signal. It can be used as identifier.