What cache tables should I keep on Memcache on a multi-site server? I can spare 64-96Mb of memory on my VPS running a dozen Drupal 6 and 7 sites. In this situation, what cache tables should I keep on Memcache, and why?

I realize cache_update and cache_form are not proper caches, but my question rather assumes it's better to have a few well-cached tables than lots of poorly cached ones. Is this assumption correct?
I guess the question is if and when those tables would be "poorly cached". This will depend completely on the actual request load of your website. Without detailed insight it's hard to give you a concrete recommendation, except that "premature optimization is the root of all evil" (D. Knuth).

Therefore, simply start with caching all tables in Memcache and then measure how effective (hits vs. misses) Memcache works. You could do this with the Memcache admin module or, with a bit more effort, using Munin. Then you'll see if you actually should shift some RAM from the more ineffective tables to the more frequented ones. That's exactly what we do to optimize Memcache on our Drupal hosting clusters.