Regarding how to find a good partitioning of values for 2-way braching,
here's a suggestion, it's nothing amazing but might help as a starting
point:

        The variable ordering heuristic selects which variable to branch
on next, and has a dramatic effect on search time. As you can imagine,
one which is quick to calculate but mildly inccurate might be rougly equal
in usefulness to one which is slower to calculate but more accurate. I    
implemented two different [variable ordering] heursitics in NB-satz, MOMS
and UP (short for unit propagation). They are both explained in my report,
the MOMS one is quite intuitive and widely known, the UP one is well
presented in the Chu Min Li paper, referenced in my report (I couldn't  
find it on the web anywhere, but your local university might have the 
IJCAI '97 conference proceedings). Basically the UP heuristic does a   
"lookahead" which is this:
        - A number of candidate variables are chosen for further
          examination.
        - These variables are examined, one at a time. This means that the
          first candidate variable is taken as the branching variable, the
          branch is made and each of the 2 resulting subtrees are given a    
          score. The original formula is then restored and the same is
          done for the second and third candidate variables and so on ...
        - When all of the candidate variables have been scored, the one 
          with the highest score is chosen to be the branching variable.
          The UP heuristic typically scores based on the amount of unit   
          propagation acheived in each of the resultant subtrees.
So basically a few candiaidates are chosen (to restrict the amount
of work to be done - the lookahead step is typically quite expensive
so a restriction can be efficient) and the effects of branching on  
each of them are assessed. Now for my idea (finally!) - maybe something 
similar could work for finding the optimal set partitioning? There could
be a restriction to get the number of lookaheads down to a reasonable  
figure, possibly by restricting the sizes of the two partitions to be
roughly equal, or forcing them to be skewed one way (e.g. {1,4},
{2,3,5,6,7,8,9}). Then the lookahead step could again be scored by the
amount of unit propagation (or semi-unit propagation, or a weighted
combination of the two) and the best chosen, just as in the UP heuristic. 
          
Seeing as the UP heuristic (basically a trial-and-error test on all likely
candidates) manages to work well, maybe the same technique could be 
applied to the value-set partitioning problem?