Eso parece un problema puntual con tu ROM y/o Market. No es normal que desinstales una aplicación y que luego te diga que sigue instalada.
No, no es que aparezca instalada, aparece es comprada y por ende no se deja comprar "otra vez" yo tengo el mismo problema no me acuerdo con cual app y no se como solucionarlo tampoco ...