  Let $A$ be a pseudo-differential operator with symbol $q(x,\xi)$. In this
paper we derive sufficient conditions which ensure the existence of a solution
to the $(A,C_c^{\infty}(\mathbb{R}^d))$-martingale problem. If the symbol $q$
depends continuously on the space variable $x$, then the existence of solutions
is well understood, and therefore the focus lies on martingale problems for
pseudo-differential operators with discontinuous coefficients. We prove an
existence result which allows us, in particular, to obtain new insights on the
existence of weak solutions to a class of L\'evy-driven SDEs with Borel
measurable coefficients and on the the existence of stable-like processes with
discontinuous coefficients. Moreover, we establish a Markovian selection
theorem which shows that - under mild assumptions - the
$(A,C_c^{\infty}(\mathbb{R}^d))$-martingale problem gives rise to a strong
Markov process. The result applies, in particular, to L\'evy-driven SDEs. We
illustrate the Markovian selection theorem with applications in the theory of
non-local operators and equations; in particular, we establish under weak
regularity assumptions a Harnack inequality for non-local operators of variable
order.
