It seems to me like a spring-mass system would be another good thing to try here. That would give you similar behavior to hill climbing, but would also be better at avoiding local minima since I can push neighboring labels away.
I thought the article was well written and interesting but I had the same reaction you did: the first thing I would have tried would have been a force-graph.
Thanks for your comments. Plugging in a Physics engine to do just that did cross my mind but I ended up using more traditional optimization algorithms b/c they're incredibly easy to implement. Plus, I had worked with them before.