In this paper the authors address the problem of internal consistency in trajectory surface hopping methods, i.e., the requirement that the fraction of trajectories running on each electronic state equals the probabilities computed by the electronic time-dependent Schrodinger equation, after averaging over all trajectories. They derive a formula for the hopping probability in Tully's "fewest switches" spirit that would yield a rigorously consistent treatment. They show the relationship of Tully's widely used surface hopping algorithm with the "exact" prescription that cannot be applied when running each trajectory independently. They also bring out the connection of the consistency problem with the coherent propagation of the electronic wave function and the artifacts caused by coherent Rabi-type oscillations of the state probabilities in weak coupling regimes. A real molecule (azobenzene) and two ad hoc models serve as examples to illustrate the above theoretical arguments. Following a proposal by Truhlar's group [Zhu et al., J. Chem. Phys. 121, 7658 (2004) Zhu et al., J. Chem. Theory Comput. 1, 527 (2005)], they apply a decoherence correction to the state probabilities, in conjunction with Tully's algorithm, and they obtain satisfactory results in terms of internal consistency and of agreement with the outcomes of quantum wave packet calculations.