This appears to be multi-arch bug. If system has extra architectures configured, some "Architecture: all" packages will be missing from "apt-cache pkgnames" output. This bug also appears to affect some achitecture-dependent packages that are missing from the foreign architecture.