There seems to be no end to the Websites claiming to have millions, if not billions of records online. In case you were wondering, here is another site with a huge collection of online records. The site is called Genealogyarchives.com . It is a company whose only location is shown in Nebraska. They have a newer Website with a significant number of records, as of 18 November 2009, they claim 1,035,043,627 records with the number changing as you watch. At the time of this writing they have 75 data collections, including some state specific records.
In searching the records, it seems that the results are not too focused. I looked for a birth record, which according to the list of resources should have been in the database, of a relative born in Utah and all of the names returned were for other states. There also doesn't seem to be a way to search a specific collection of records but you can search by category.
You have to give a credit card number to get the seven day free trial, but your card will automatically be billed for $39.95 every 12 months unless you cancel your subscription. I was given a free trial for writing an article for their Expert Series, but I have not used the service very much.
This is obviously a site to watch to see if they have the category of records you are interested in.