There is a Gmail community at Orkut with currently 899 members. Over there I found a way to check if a Gmail account username was in use or if it was available.

You simply went to a URL and it would tell you.

The URL was: https://www.google.com/accounts/CheckAvailability?Email=YourUserName

You simply replace "YourUserName" with the name you want to check the availability of.

A couple of days ago this URL was no longer reporting back the availability of the Gmail usernames. There is belief that Google added an "encryption key to the checker now so people can't take advantage of their system."