 <p>Alright we've found the answer: we had 2 credentials and apparently used the wrong one in our APK. We switched around the Signing-certificate fingerprint so that the fingerprint in the APK and in play services match and now it's working.</p> <p>The strange thing is that everything seemed to work and we've never gotten any feedback from google that something was wrong...</p> <p>Thanks for your attention to this problem!</p>