That's bad. In fact, apt-cache madison paketname does not work as expected.
Ubuntu:
# apt-cache madison agrep
apgrep ... multiverse/Packages

I hope that RPM (with Meego) will be implemented more complete than APT (with Maemo).