flickr deals with that problem by manually moving power users if necessary. They have a tool that lets them do that. See: http://highscalability.com/how-flickr-handles-moving-you-ano...

In practice it's going to be very rare that you'll overwhelm a single shard and adding an extra layer to point to where people actually are is quite simple and fast. You can use a simple cache key (read-through cache of course) that, if it exists means the user is on a specific shard, overriding the default algorithmic pick.