It is hard to get an accurate estimate of the actual number of DVD titles available at most sites - they either don't say or the numbers are a little "optimistic". I've tried to estimate some of the companies where I can (mainly those that use a sequential inventory numbering system). Most companies split multiple disc sets into separate rentals, so the estimates represent rentable "discs", not titles. A season of a TV show like "NYPD Blue" might be 6 discs.

Aside from ZIP, I get no information from the companies, and these should be taken as estimates only. The numbers may not correspond with the percentage from my test database, since some companies may have a large number of titles in specialty areas, or for one reason or another just have more of the movies I'm testing with. Also, there is no way to know how many copies of a title a company has.

Company
Claim
Best Guess
 Notes
ZIP
53,000
46,000+
 At one time I was getting a periodic update on the actual ZIP count directly from their president, and more recently I've been basing the estimates on my own retrievals (the two were always fairly similar). Their public "advertising" number includes upcoming, on order, out of print, etc., as well as some "TBA" titles where there is no DVD in existence yet, although you can ZipList all of these - you can get see a more detailed breakdown here.
DVDflix
8000
~8000
 I base my guess on the number of pages (10 per page) of their "All Genre" listing displays (thanks to "M. A." for the tip). They've been increasing their claimed number (from 5000 to now 7000 and 8000); they are finally starting to approach this number but it would have originally just been marketing piffle).
Cinemail
20,000+
20,000+
 Based on counts returned by their search feature, and actual listings.
Canflix 20,000
9000+
 As of March 2006 I've recently resolved many of my issues with Canflix regarding their inventory claims. A conversation with one of the owners in early March 2006 put the count at around 8800. This may have included video games, some on order titles, etc. There is also a technical oddity regarding some titles which are incorrectly reported while they are with the associated Blairmore video store. I'll try and get a more accurate number once things have settled down a bit. The 20,000 title figure (actually closer to 25,000) can be considered their "virtual" inventory of listings - there are around 15,000 titles on their system which they can order based on customer demand, etc.
DVDHype
10000+
Relay
~3000
 Based on count returned by their search feature.
Starflix
30,000
< 9000
 I can't find any evidence for anywhere near their 30,000 claim, or even their previous 23,000 or 16,000 claims, which still appear in some places on the website. My checks in December 2004 produced no more than 8000-9000 active inventory discs that came up via the search engine, and some unknown portion of this may not be actually product (see the "Wolfgang Petersen pack" example. And there is no way of determining whether some of this is "virtual" inventory like Canflix.
DVD-Rental
~3500
 Not actively functioning. They have a little over 4000 listings, plus almost 500 videogame titles. But some of this appears to be "virtual inventory", including most of the Criterions.
DVDsToYourDoor
~2500
 CLOSED late 2006. I previously counted up the totals from the various Genre pages (like DVDflix, they have non-sequential inventory numbers). As of sometime in October 2004 they changed the layout of their genre pages, but I've found an alternative method which seems to work as well. They have gone two months since January 31, 2006 without adding any titles, and seem to be going moribund.
RentaDVD
10,000
~8000?
 CLOSED May 2005. Around 8000 inventory IDs, and a few holes. However, RentaDVD is unique in that it ships most 2-disc sets as a single rental. I'd guess there might be 3-400 of these, probably enough to at least offset any unused inventory slots. Their "Availability" indictors in the member queues also seem problematic, and specifically newly added items seem to be marked "Long Wait" instead of a specific "On Order" indicator, so there is no way of knowing for sure how many of the items may not yet be in stock.
MovieBuffs
3200+
 CLOSED August 2005. Based on id numbers.
VHQ
~10,000
 CLOSED September 2005 (bought by ZIP) A few inventory numbers are not in use, and some are video games, which I eliminate from the count. My understanding is that VHQ emphasizes having high availability of the titles they do carry, especially new releases. The number on the main page should be relatively up to date - I'll try and check it every week or two.
MoviesForMe
20000
7000/18500
 CLOSED September 2005 (bought by ZIP) As of August 2004, they've now got a large number of titles (18,000+) in their database. However, a majority of these are "order on demand" and haven't actually been purchased yet. They supposedly did add quite a bit of physical stock as well - they gave me a ballpark figure of around 7000 titles (which would be a doubling of what they had previously). This means that their figures on my inventory charts are not strictly comparable, since I can't tell which titles are virtual inventory. As long as they order things in as people request them this should work acceptably, although it would be nice if there was an indicator showing whether a title is owned or "order on demand". Caveat emptor - just remember that the ZIP number is actual, while M4M's is virtual - it can make a difference if they don't order in requests, have trouble with specialty or import orders, etc.
JurassicDVD
10000+
~7000
 CLOSED October 2005 Their site started out with a 19,000+ claim - they brought it down to 6000, but it looks like it is back to 10,000+, which seems to be an overstatement.