A decent memcached instance on modern hardware can easily push several 100K updates/sec . Couldn't you do the same with a pool of sharded memcached servers? Compute the MD5 hash of the string you want to count (which can be 16 strings, from the top-rated comment above), and just use that as the key.
We've seen people push 750K QPS on an InnoDB via HandlerSockets http://news.ycombinator.com/item?id=1886137 , so imagine what you could do with a sharded pool of 20 InnoDB servers.
Again: if I'm missing something, I'd love to learn.