We had the same problem at Justin.tv with the video servers, with the added wrinkle that every choice had the potential to meaningly affect load for an hour or more. We eventually ended up putting extremely detailed information into a central database for the load balancer so that it could consider not only server load, but also the load on all of our internal and external network links.

We also had to keep track of how many people were on the webpage for a channel when it went live so that we could preemptively replicate the video stream to enough, but not too many, servers.