Thanks for the detailed reply. Sorry, I wasn't meaning to teach you to suck eggs. That part of my reply was for readers who don't know much about Drupal beyond it having a strange name.
Interesting: I didn't know about the table lock on cache! Are you using Drupal 6? I've just done a search, but didn't find anything. I did find a status report I didn't know about! At admin/reports/status/sql which shows lock hits amongst other things. Maybe you are on Drupal 5? The cache updates I found where all straight inserts/updates or deletes. But whatever - I'd say that you were right in moving caching to memcached if you have to support millions of pageviews.
Yes - I agree the cache layer needs PHP execution, and that's not so great. Actually, IMO it's not the PHP, but that it's a hit against the database, even though it is a single query. A hit against the file system would avoid the whole DB connection and query. Drupal Boost caching module wouldn't bring huge benefits for you because you have lots of logged in users, but it uses static files and doesn't hit the database.
Block cache can be efficient at cutting down database hits and code execution. And if you are using Views2, it will also use block caching for HTML and queries. It has options for lots of different caching strategies - from one for everyone through to per user per block. Block caching not well documented though.
One thing that I'm not sure of is why one website would interfere with the cache of another if you are not sharing content. [Readers: you can configure Drupal to use a single database for all websites, or multiple databases. If you have a single database, then you can configure each installation to use a different set of tables, through setting a prefix to the table name. It's very unusual to share any of the cache tables across sites except in the shared-content scenario, where the same content is being presented on more than one website.] Maybe I've misunderstood. It might be that the sites are running on a cluster against a db shared across the cluster. In this scenario, I can imagine one machine locking others out, though I'm not sure where in the code a table lock is.
Multisite: Good points and bad points. The management of update is the bad point, when you put in a new module with database upgrades. You have global downtime unless you do progressive updates by putting the module first in the specific directory for each of the particular sites and running update for that site. But it does lower the admin cost.
SQL rewriting works in some circumstances. See hook_db_rewrite_sql. [Readers: The base problem is that it's difficult with modularity to avoid explosion of queries. This is true of all modular systems with database interactivity. You can avoid it if one module is intimately aware of another, and then the two can co-operate, though this is context dependent. For instance - if the first module loads the user details (name, user account, email, etc), and a second, optional, module loads a user profile, then you could cut down on the queries by including the user profile columns as part of the user table, and loading the two at the same time. Modularity, however, is not your friend here - to make the management of a profile module easy, it's much better to have it in its own table. But now you are doing table joins or loading one and then the other. If you have a heavily customised system, then you can make the joined table by hand, and modify the queries. You can do this either by changing the core code, or by rewriting the SQL on-the-fly, by writing a new module. With the second option you can leave the core alone, and your changes are overlayed, at the cost of a small drop in performance of the PHP (since there's an extra function to run). The PHP drop is almost certainly negligible compared to the database speed-up, except where the database is already in memory.]