You could try inspecting the output of
$ pkgutil --pkgs
to see if any of the names look like the package that claims to be installed, then
$ pkgutil --pkg-info thatpackage
to see where it was installed. If it's not actually found there, you could try
$ sudo pkgutil --forget thatpackage
and see if the App Store will let you re-download; but at that point I'd probably contact App Store support first, as mucking with the package database might cause bigger problems (like, conceivably, forgetting that you ever bought the program — although I would hope Apple's programmers were smarter than that).