How can I see all versions of a package that are available in the archive?

As far as I understand your requirements, the madison option for apt-cache does what you want:

madison /[ pkg(s) ]
apt-cache's madison command attempts to mimic the output format and a subset of the functionality of the Debian archive management tool, madison. It displays available versions of a package in a tabular format. Unlike the original madison, it can only display information for the architecture for which APT has retrieved package lists (APT::Architecture).

On my computer:

$ apt-cache madison f-spot
    f-spot | 0.7.2-1~ppa~lucid0 | http://ppa.launchpad.net/f-spot/f-spot-ppa/ubuntu/ lucid/main Packages
    f-spot | 0.6.1.5-2ubuntu7 | http://ro.archive.ubuntu.com/ubuntu/ lucid-updates/main Packages
    f-spot | 0.6.1.5-2ubuntu6 | http://ro.archive.ubuntu.com/ubuntu/ lucid/main Packages
    f-spot | 0.6.1.5-2ubuntu6 | http://ro.archive.ubuntu.com/ubuntu/ lucid/main Sources
    f-spot | 0.6.1.5-2ubuntu7 | http://ro.archive.ubuntu.com/ubuntu/ lucid-updates/main Sources

I hope this is what you need. It also includes the ppas.

The command

apt list -a <package name>

is the equivalent of madison.

The rmadison program from the devscripts package will remotely query the Ubuntu archive and give you the status of a package in all supported releases, not only those you have locally insatlled. This is slightly more than what you want, but should get the job done easily.

Example:

lfaraone@stone:~$ rmadison sudo
      sudo | 1.6.8p12-1ubuntu6 |        dapper | source, amd64, i386, powerpc
      sudo | 1.6.8p12-1ubuntu6.3 | dapper-security | source, amd64, i386, powerpc
      sudo | 1.6.8p12-1ubuntu6.3 | dapper-updates | source, amd64, i386, powerpc
      sudo | 1.6.9p10-1ubuntu3 |         hardy | source, amd64, i386
      sudo | 1.6.9p10-1ubuntu3.8 | hardy-security | source, amd64, i386
      sudo | 1.6.9p10-1ubuntu3.8 | hardy-updates | source, amd64, i386
      sudo | 1.6.9p17-1ubuntu3 |        jaunty | source, amd64, i386
      sudo | 1.6.9p17-1ubuntu3.3 | jaunty-security | source, amd64, i386
      sudo | 1.6.9p17-1ubuntu3.3 | jaunty-updates | source, amd64, i386
      sudo | 1.7.0-1ubuntu2 |        karmic | source, amd64, i386
      sudo | 1.7.0-1ubuntu2.4 | karmic-security | source, amd64, i386
      sudo | 1.7.0-1ubuntu2.4 | karmic-updates | source, amd64, i386
      sudo | 1.7.2p1-1ubuntu5 |         lucid | source, amd64, i386
      sudo | 1.7.2p1-1ubuntu5.1 | lucid-security | source, amd64, i386
      sudo | 1.7.2p1-1ubuntu5.1 | lucid-updates | source, amd64, i386
      sudo | 1.7.2p7-1ubuntu1 |      maverick | source, amd64, i386

before you can use rmadison you must install the devscripts package:

sudo apt-get install devscripts