Right way to get the list of installed packages matching a pattern

As well as apt-cache policy, described in Braiam's answer, you can use apt-show-versions and apt-forktracer.

apt-show-versions by default will list all installed packages with the suite they come from, their version and whether they can be upgraded; for example

afl:amd64/experimental *manually* upgradeable from 1.28b-1 to 1.36b-1
agedu:amd64/testing 9723-1 uptodate
devio:armhf 1.2-1 installed: No available version in archive

With the -a option it lists the installed version and all available versions in all the repositories you have configured:

afl:amd64 1.28b-1 install ok installed
No stable version
No testing version
No unstable version
afl:amd64 1.36b-1 experimental ftp.fr.debian.org
afl:amd64/experimental *manually* upgradeable from 1.28b-1 to 1.36b-1
agedu:amd64 9723-1 install ok installed
No stable version
agedu:amd64 9723-1 testing  ftp.fr.debian.org
agedu:amd64 9723-1 unstable ftp.fr.debian.org
No experimental version
agedu:amd64/testing 9723-1 uptodate

apt-forktracer lists the packages which don't come from the standard repositories or whose installed version doesn't match those available in the standard repositories:

afl (1.28b-1) [Debian: 1.36b-1]
bb (1.3rc1-8.2) [Debian: 1.3rc1-8.1+b1 1.3rc1-8.1+b1]
biew (5.7.3.1-0.1) [SK2: 5.7.3.1-0.1]

Search for packages that are manually installed, and that are a mandatory or recommended dependency of an installed package. Aptitude can do that.

aptitude search -q -F %p '?installed !?automatic (?reverse-depends(?installed .*) | ?reverse-recommends(?installed .*))'

I don't think there's a way to indicate what dependency was found for each package. If you want that information, Python would be the way to go. This very quick-and-dirty script seems to do it (mostly, I think it may be incorrect in some non-straightforward cases involving disjunctions, version dependencies, pre-depends, …).

#!/usr/bin/env python2
import apt
packages = apt.Cache()
covered = {}
# Inverse dependency computation: for each installed package, record which
# packages require it (as Depends: or Recommends:).
for p in packages:
    if p.installed:
        for l in p.installed.dependencies + p.installed.recommends:
            for d in l:
                if packages.has_key(d.name) and packages[d.name].installed:
                    if not covered.has_key(d.name):
                        covered[d.name] = []
                    covered[d.name] += [p.name]
# Print out the manually installed packages that are required by another
# installed package, as well as the requiring package(s).
for p in sorted(covered.keys()):
    if not packages[p].is_auto_installed:
        print(' '.join([p] + covered[p]))