Simply using the list of installed files to search against is not a hack, is well documented and works exactly as expected. Also, if a file wasn't installed through the package manager, dpkg will tell you as well:
$ dpkg -S weeblefrob
dpkg-query: no path found matching pattern *weeblefrob*.
$ dpkg -S /usr/bin/weeblefrob
dpkg-query: no path found matching pattern /usr/bin/weeblefrob.
Only one version of any given package may be installed at any time and to see which version is installed you can use either dpkg -l $package or apt-cache policy $package (this tells you which version would get installed, too). If you want to search for files in all packages (even those not installed), you can use apt-file.