Column balancing seems to work now. I had to modify BreakingAlgorithm to add best records for parts which are too short. Furthermore, it took an additional computed value to tweak the balancing. It effectively makes shorter trailing parts preferred.
xmlgraphics/fop/trunk/src/java/org/apache/fop/layoutmgr/BalancingColumnBreakingAlgorithm.java