You can get list of available versions of a specific package using rmadison utility from devscripts suit. It remotely polls packages database to show "official" information for Debian/Ubuntu/Backports, regardless of repositories you have configured on your system.
$ rmadison -u debian,ubuntu,bpo mercurial | cut -d "|" -f 1-3 debian: mercurial | 0.9.1-1+etch1 | etch-m68k mercurial | 0.9.1-1+etch1 | oldstable mercurial | 1.0.1-5.1 | stable mercurial | 1.5.1-2 | testing mercurial | 1.5.2-1 | unstable ubuntu: mercurial | 0.7-8 | dapper/universe mercurial | 0.9.5-3 | hardy/universe mercurial | 1.0.1-5.1~hardy1 | hardy-backports/universe mercurial | 1.1.2-2ubuntu1 | jaunty/universe mercurial | 1.3.1-1 | karmic/universe mercurial | 1.4.3-1 | lucid/universe mercurial | 1.5.2-1 | maverick/universe bpo: mercurial | 1.0.1-5.1~bpo40+1 | etch-backports mercurial | 1.3.1-1~bpo50+2 | lenny-backports
Probably it's not a big deal to implement such functionality for your own private repos.
I believe it could help developers to choose the right distro version or adjust project/feature requirements on an early project planning stage. So much working hours could be saved for sysadmins working on a "private" backporting, who're responsible for the deployment of those new shiny betas to production systems.
I wish we'd have some alternative for RPM-based distros someday.
UPDATE 22 May 2010:
Of course we have it already :) I've recently found whohas utility, which goes far beyond Debian family. It's able to show versions of available software for other distributions (Arch, openSUSE, Gentoo, FreeBSD and even more - 14 distros/repos at the moment, see list below).
"archlinux", "debian", "fedora", "fink", "freebsd", "gentoo", "macports", "netbsd", "openbsd", "opensuse", "slackware", "sourcemage", "ubuntu", "opkg"
Though there are some problems. whohas version 0.23-3 lacks support for CentOS and Fedora 10 reached it's EOL (packages moved to archive), so most valuable piece of information is not available by default.
