When we use the BRST formalism for the conformal symmetry, it's because we want to preserve the conformal symmetry as an efficient tool to do the calculations of the interactions.
Interactions of strings, which are composed out of splitting and joining interactions whenever you "slice" any history, are described by a world sheet in spacetime. We usually analytically continue to the Euclidean world sheet embedded in a spacetime that may actually be kept Minkowskian. The only manifestly Lorentz-covariant quantities that may be calculated are the scattering amplitudes.
Scattering amplitudes are calculated as sums of all histories. Each history is a world sheet which has some topology - a genus $h$ Riemann surface with $b$ boundaries and $c$ crosscaps (it has $h$ handles). There exists a "moduli space" of such Riemann surfaces, one must integrate over it to get the amplitude (it's the residual integral from the integration over the auxiliary world sheet metric that can't be fixed by the conformal gauge), and the prescription for the measure is uniquely determined from the BRST formalism. There are no gauge-invariant local observables in quantum theories of gravity:
Diff(M) as a gauge group and local observables in theories with gravity
Standard textbooks derive all these formulae and one never encounters anything such as the "Gribov problem" along the way. In fact, this term will remain unknown to any student who learns the thousands of pages of the introductory string theory textbooks. This is no coincidence. Much more generally, it is just an illusion that there is an inevitable problem of this kind. One may always find a way to totally circumvent it. As has been discussed in this question:
Why do Faddeev-Popov ghosts decouple in BRST?
the BRST formalism is just a formalism - not a question about "new physics".
In principle, all of its physical - i.e. in principle measurable - results could be obtained by other formalisms, too. The Gribov problem is a "non-perturbative ambiguity". However, whenever we have a theory defined perturbatively, we must classify all possible internally consistent (which includes unitary) non-perturbative completions of the theory (it may be unique and it may be non-unique). The previous sentence defines what it means to study the non-perturbative physics properly and this requirement is true regardless of the formalism one uses.
So one may face a Gribov problem but it is just a problem with a particular formalism. Physical criteria must be imposed to find out whether non-perturbative physics can be consistent at all, and whether it is unique, and with a sufficient patience and skills, one may always find the answer to the physical question - i.e. to classify all possible ways to non-perturbatively complete the theory. If one doesn't use all the physical arguments and clever tricks, he may get stuck with a Gribov-like problem in his calculations - but it's just his problem, not a problem of physics. The latter always has answers.