In principle, the above reasoning gives a nice large space of PDOs that satisfy my criteria. But are there any more? I think there are (see below).
Now, suppose that I cannot ignore time derivatives. Willie's suggestion is to write the equation $L[u]=0$ in evolution form $\partial_t v + Av=0$ and exclude $L$'s for which the evolution equation is well posed as an initial value problem. But not all such $L$ can be excluded, since not all initial data generates solutions that satisfy the boundary conditions (decay at infinity along any space-like direction). I'm thinking that there should be a geometric condition involving the background null cone and the characteristics of $L$ or the zero set of $P(\xi)$. For instance, if TO BE CONTINUED...$L=-c^{-2}\partial_t^2+\partial_x^2$ with $c>1$, then the corresponding equation has infinitely many solutions parametrized by Cauchy data on $t=0$. However, these solutions would correspond to waves pulses propagating along the $x$-axis at a speed faster than the background speed of light. On the other hand, the solution $u(t,ct)$ must vanish for large $t$ as $(1,c)$ is a space-like vector. I believe this is enough to show that this $L$ also admits only trivial solutions. My reasoning here is based on the exact representation of solutions via the D'Alambert formula, but that doesn't generalize easily. Any idea what kind of geometric condition could be used for more general operators?
Ultimately, I'd like to know something about the geometry of the space of operators that satisfy my criteria. Say I fix the maximal order to make things easier. The space is clearly not linear, but could it be convex or the complement of a convex set? (These last guesses are probably not right. I'm just throwing out ideas.) I'd be happy if I could understand this space for just first and second order operators, preferably with hints of how this understanding could generalize to higher orders.