The strategy you list is adaptive, i.e, depending on the outcome of a weighing, you do different things. An interesting special class of solutions is fixed strategies, where you just have 3 fixed weighings such that no matter how the one ball is odd, you will detect it. Unfortunately, I know that my analysis is not complete, and I'm not sure that any such strategies exist (I suppose I could google, but I haven't yet). I wrote some very basic brute search code to look for a fixed strategy, but came up cold.

The reason I am drawn towards fixed strategies is that, if they exist, they have the benefit of having a much simpler representation. You can look at a fixed strategy as a 12 x 3 table, filled with L, R and - (or L, R, and ~ if you like), to denote whether a ball is on the left or right side of the scale, or not weighed in a certain round. Example:

  L L L L R R R R - - - -
  L L - - R R - - L R - -
  L - L - L - R - R - R -
[download]

This strategy says to weigh balls 1-4 vs balls 5-8. Then weigh 1,2,9 vs 5,6,10. Then weigh 1,3,5 vs 7,9,11.

It's easy to check whether this gives a real solution. First of all, in order to give you any information about ball weight, each round has to have the same number of balls on the LHS and RHS of the scale. Then, you have to pretend the odd ball is each of the 12 balls and see whether all other candidates would get logically eliminated. If the odd ball is one that is measured, then the scale tips so you can throw out the ones that weren't measured. If the odd ball is not measured, the scale balances, so you can throw out the ones that were measured. In code, that looks like this (with the table being represented as a 2d, 3x12 array):

sub check_scheme {
    my @scheme = @_;

    ## check that each round measures the same amount of balls
    for my $round (0 .. 2) {
        my $lhs = grep { $scheme[$round][$_] eq "L" } 0 .. 11;
        my $rhs = grep { $scheme[$round][$_] eq "R" } 0 .. 11;
        return 0 if $lhs != $rhs
    }

    ## simulate the scheme with each of the balls being the odd one
    for my $item (0 .. 11) {
        my @candidates = (0 .. 11);

        for my $round (0 .. 2) {
            if ($scheme[$round][$item] eq "-") {
                @candidates = grep { $scheme[$round][$_] ne "-" } @can
+didates;
            } else {
                @candidates = grep { $scheme[$round][$_] eq "-" } @can
+didates;
            }
        }

        ## by this point we should have eliminated all but one ball!
        return 0 if @candidates != 1;
    }
    return 1
}
[download]

Unfortunately, I know that this analysis is incomplete, because (depending on the statement of the problem) you may be able to use information about the direction of the scale and keep track of which balls were on sides of the scale that went up and down. The only information I assume we use here is whether or not the two sides were equal. In fact, now that I'm writing this, I think a basic counting argument shows that there is no fixed strategy that works unless you use information about whether balls were in the heavy or light side of the scale (Update: Indeed, look at the "L" or "R" entries as 1s and the "-" entries as 0. For two balls to be distinguished, they must at some point have mismatched 0/1's in their column. There are 8 ways a ball can have an assignment of 0/1's, but there are 12 balls. Conclusion: some pair of balls must be indistinguishable in this very simple scheme).

Oh well, it was a nice attempt at a simple analysis, but it was too simple to yield any solutions. My feeling is that this analysis could be extended by keeping a two lists of candidates (the possibly heavy balls and the possibly light balls), seeing which way the scale swings, and making the logical deductions. Feel free to expand on it, but unfortunately I need to go get other work done this morning ;)