Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory performance, but there is a plethora of extensions/enhancements available.
I don't have experience with the specific game you mentioned (Connect6), but from a quick look ...
If I am correct, the branching factor is the maximum number of successors of any node
You are correct, they should also be the immediate ones:
If 11 is the goal state and I start going backwards, is 10 considered as successor of 5? Even if it do not leads me further to my start state 1?
No, there is also a bit of misunderstanding of bidirectional search: ...
The branching factor is important, as it limits the effectiveness of search.
However, the branching factor in chess is already too high to effectively search without techniques that reduce the size of the search space. Even with millions of tests per second, a computer can only check a small fraction of the possible future games in order to find results in ...
As you mentioned in the question, you cannot solve all problems with decision trees. Decision trees usually works well in a turn-based game with a good heuristic function, but in RTS games takes a different approach.
In the case of a very complex RTS game, one could implemented a rule-based AI. For example
given it is the early game use all units to scout ...
As you found $N$ is the number of nodes that are expanded. The cost of expansion of each node is equal to the number of children of that node. Hence, we use $b^*$ for each node. In other words, the total number of nodes that are involved in the expansion process is $N \times b^*$.
I'd say that the leaves per se count, too, but only if they're real leaves, like e.g., checkmate positions in chess.
Such a node has really no children and no further calculation is needed. Unlike with nodes which weren't expanded yet.
Note that always counting the leaves provably leads to (n-1)/n for every n-node thee!