Use Memcache?
Upgrade to the 1.4.0 server and, if you’re PHP-based, the 3.x PECL module.
The server is much faster (I didn’t think that was possible), and the consistent hashing support in the PECL client’s new MemcachePool class makes server-pool management very easy. The biggest gain from consistent hashing is that you can add or remove servers from the pool without invalidating all of your existing keys — the more cache servers you have, the more important this becomes.
Oh, and if you want to test it with a bunch of servers without buying them, there’s a convenient Amazon EC2 system image with 1.4.0.