The final condition for a realistic theory in physics is that its predictions (of scattering amplitudes or correlators etc.) have to agree with observations. This implies that the predictions have to be consistent and obey some general consistency conditions (unitarity, non-negativity of probabilities, some symmetries, locality or approximate locality, and so on).
For theoretical theories, it's just the general consistencies that hold. Now, the task is to classify all possible theories and learn how to calculate with them.
It turns out that the Euclidean spacetime or world sheet is simply a simpler, more straightforward, more free-of-subtleties approach to produce a machine that calculates some scattering amplitudes or other observables.
At least formally, the Euclidean theories may be continued to analytic ones and vice versa. For nontrivial spacetime topologies, the Euclidean objects are likely to be more manageable. For example, the world sheets in string theory (think about a torus or pants diagrams etc.) are much more well-behaved in the Euclidean signature so we may consider this approach "primary". Covariant calculations in string theory are almost always done with the Euclidean ones. The result may be continued to the Minkowski momenta etc. and some of the consistency conditions above are still guaranteed to hold because of some properties of the complex calculus.
In the light-cone gauge, we may work directly with the Minkowski-signature world sheets. But we pay the price that the interaction points where strings split or join are singular and the direction of the "future time" is ambiguous. We must also include contact terms, higher-order interaction terms, to deal with some divergences caused by the singular world sheets, but when these things are summed over, we may prove that the resulting amplitudes agree with the covariantly computed ones (in the Euclidean signature).
Gravity in $d\geq 4$ (and maybe 3) suffers from the "negative norm conformal factor". The Euclideanized Einstein-Hilbert action $\int R \sqrt{g}$ is no longer positively definite. In particular, if you consider scalar waves that scale the metric by an overall number, $g_{\mu\nu}=e^F\eta_{\mu\nu}$, and derive the kinetic term for $F$, it will have the opposite sign than the kinetic term for other components of the metric tensor (the physical polarizations of the gravitational waves, like $g_{xy}$).
It follows that the action will be bounded neither from below nor from above, and $\exp(-S_E)$ in the Euclidean path integral will diverge in some region of the configuration space. In this sense, people believe that the Minkowskian path integral must be the "more kosher one" for higher-dimensional gravity. But this is a bit empty statement because at the quantum level, higher-dimensional gravity obtained as a direct quantization of Einstein's equations is inconsistent, anyway. And string theory which is consistent and contains gravity doesn't give us any tool to directly rewrite the path integral in terms of spacetime fields including the metric; it is not a field theory in the ordinary sense. So the preference for the "Minkowski signature" is a bit vacuous. After all, the Minkowskian action isn't bounded from either side, either. This is considered "not to be a problem" because the integrand is $\exp(iS)$ which still has the absolute value equal to one, so it doesn't diverge. But I would personally say that the unboundedness of the Euclidean action is the "same" problem for the Minkowskian path integral.
Quite generally, the Wick rotation is extremely important in quantum field theory and it is actually even more important in quantum gravity or places with many spacetime (or world sheet) topologies, i.e. in situations where one has many different "time variables" in which we might try to expand things. One shouldn't be afraid but at the end, whatever theory he deals with, he gets some amplitudes whose self-consistency (and/or consistency with observations) must be verified. With some "good rules of behavior" while Wick-rotating, one may be "pretty sure" that some tests will be passed.