Although Ballmer could still be incorrect, because a 'sufficiently logical' player would also presumably know that he could pick numbers that'll be the most difficult to find via binary-search, so by the same logic you could also meta-game it, and assume any number that can be found in 5 steps with a binary search is immediately out. This would narrow the search space to only 37 numbers, which can then easily be found within 5 guesses.

But he also knows that you know that he could pick numbers that will be the most difficult... So could then pick one of the numbers that actually are guessable within 5 guesses to trick you.

But then you also know that he knows that you know that he could pick difficult numbers too.

I'm not entirely sure if this invalidates Ballmer's advantage, but I would be interested to know what the 'perfect' strategy would be for this game considering the meta-game.