Totalmente de acuerdo con Aglos.
Pensándolo, la solución sería fácil ¿no?: si tu pagas una aplicación en el Market, queda registrada no?. Pues lo contrario también se podría aprovechar, si no está registrado el pago (en las de pago, por supuesto), que no funcione la aplicación... Luego ya saldrían ñapas para evitarlo, pero es un comienzo...