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 donde se instaló. Si no se encuentra allí, puedes intentarlo
$ sudo pkgutil --forget thatpackage
y vea si la App Store le permitirá volver a descargar; pero en ese punto, probablemente me pondría en contacto primero con el soporte de la App Store, ya que el muck con la base de datos del paquete podría causar problemas más grandes (como, posiblemente, olvidar que alguna vez compró el programa, aunque espero que los programadores de Apple eran más inteligentes que eso).