How can I find out package versions available from repositories?
Aptitude is Debian's current recommended package manager (see Lenny Release Notes) and amongst other things is great for searching available and installed packages.
aptitude search ~npackage_name_regex~dtext_in_description
See section 2.2.6. in the Reference Manual: http://www.debian.org/doc/manuals/reference/ch02.en.html#_basic_package_management_operations
However, use 'apt-cache policy' to show package versions.