Así de pronto se me ocurre lo siguiente:
Iniciando un "Activity With Result" desde tu aplicación sobre la aplicación Key, y el resultado que te da la Activity de la Key lo compruebas con algún valor en tu aplicación, si coinciden es que la Key está instalada.
Lo único es que me parece muy fácil de "hackear".