[regression] apt-cache madison no longer can find some source packages

Binary package hint: apt

With the attached source.list and sources.list.d/ubuntu-security.list, apt-cache madison doesn't always work. This breaks the ubuntu-security tools for publishing security updates. Eg:

$ for i in dhcp3 openldap mysql-5.1 ; do apt-cache madison $i ; done
N: Unable to locate package dhcp3
N: Unable to locate package openldap
$

But rmadison works:
$ for i in dhcp3 openldap mysql-5.1 ; do rmadison $i ; done
     dhcp3 | 3.0.3-6ubuntu7 | dapper | source
     dhcp3 | 3.0.3-6ubuntu7.1 | dapper-security | source
     dhcp3 | 3.0.3-6ubuntu7.1 | dapper-updates | source
     dhcp3 | 3.0.6.dfsg-1ubuntu9 | hardy | source
     dhcp3 | 3.0.6.dfsg-1ubuntu9.1 | hardy-security | source
     dhcp3 | 3.0.6.dfsg-1ubuntu9.1 | hardy-updates | source
     dhcp3 | 3.1.1-5ubuntu8 | jaunty | source
     dhcp3 | 3.1.1-5ubuntu8.2 | jaunty-security | source
     dhcp3 | 3.1.1-5ubuntu8.2 | jaunty-updates | source
     dhcp3 | 3.1.2-1ubuntu7 | karmic | source
     dhcp3 | 3.1.2-1ubuntu7.1 | karmic-security | source
     dhcp3 | 3.1.2-1ubuntu7.1 | karmic-updates | source
     dhcp3 | 3.1.3-2ubuntu3 | lucid | source
     dhcp3 | 3.1.3-2ubuntu5 | maverick | source
  openldap | 2.4.15-1ubuntu3 | jaunty | source
  openldap | 2.4.18-0ubuntu1 | karmic | source
  openldap | 2.4.21-0ubuntu5 | lucid | source
  openldap | 2.4.21-0ubuntu5.1 | lucid-proposed | source
  openldap | 2.4.23-0ubuntu1 | maverick | source
 mysql-5.1 | 5.1.49-1ubuntu2 | maverick | source
$

This used to work fine on Lucid.

ProblemType: Bug
DistroRelease: Ubuntu 10.10
Package: apt 0.7.26~exp12ubuntu3
ProcVersionSignature: Ubuntu 2.6.35-14.19-generic 2.6.35
Uname: Linux 2.6.35-14-generic x86_64
Architecture: amd64
Date: Fri Aug 6 16:34:04 2010
EcryptfsInUse: Yes
InstallationMedia: Ubuntu 10.04 LTS "Lucid Lynx" - Release amd64 (20100427.1)
ProcEnviron:
 PATH=(custom, user)
 LANG=en_US.utf8
 SHELL=/bin/bash
SourcePackage: apt