本家にも同じような質問/回答があったので共有します。
http://stackoverflow.com/questions/4888027/python-and-pip-list-all-versions-of-a-package-thats-availablehttps://stackoverflow.com/questions/4888027/python-and-pip-list-all-versions-of-a-package-thats-available
ここで紹介されているyolkというツールが良さそうな感じでした。pypiで利用可能なすべてのバージョンを表示してくれるようです。
$ yolk -V sphinx
Sphinx 1.3b3
Sphinx 1.2.3