Puedes intentar inspeccionar la salida de
$ pkgutil --pkgs
para ver si alguno de los nombres se parece al paquete que dice estar instalado, entonces
$ pkgutil --pkg-info thatpackage
para ver dónde se instaló. Si no se encuentra allí, puede intentar
$ sudo pkgutil --forget thatpackage
y ver si la App Store te permite volver a descargar; pero En ese momento, probablemente me pondría en contacto con el servicio de asistencia de la App Store, ya que manipular la base de datos de paquetes podría causar problemas mayores (como, por ejemplo, olvidar que alguna vez se compró el programa, aunque espero que los programadores de Apple sean más inteligentes que eso).