I need to find general solutions to the problem $$u_{tt} -u_{xx} -u_t -u_x=0$$
I wrote the PD operator here as $P \left( \partial_t , \partial_x \right) = {\partial_{t}}^2 -{u_x}^2 -\partial_t -\partial_x$ which in turn can be factorized as $P \left( \partial_t , \partial_x \right) = \left( \partial_t +\partial_x \right) \left( \partial_t -\partial_x -Id \right)$ where $Id$ is the identity operator.
Now, the equation $Pu=0$ can be expressed by the system:
$$\cases{u_t -u_x = u+v \\ v_t + v_x =0 }$$
The second equation here has the general form of $v = \phi \left( x-t \right)$ (derived using the method of characteristics).
Then I'm left with the problem $u_t - u_x = u + \phi (x-t)$ which can be written using the method of characteristics (again) as $u_t = u + \phi(x - t)$
I realize this is some kind of ODE, that I can solve for different values of $x$: $$ u = \Psi(x) e^{t} + \Phi(x-t)$$
But when calculating $Pu$ I get $$Pu = -{\mathrm{e}}^t\,\frac{\partial ^2}{\partial x^2} \Psi \left(x\right)-{\mathrm{e}}^t\,\frac{\partial }{\partial x} \Psi \left(x\right) $$
And for $Pu$ to nullify, $\Psi$ must be $ C e^{-x}$. Thus $u = C e^{t-x} +\Phi \left(x - t \right)$. Surely, this solution is valid, but is this as general as it can be? How can I tell I didn't miss any other solution?
For the specific equation you provided, it seems unnecessary to use differential operators. Instead, it suffices to use the change-of-variable trick that has been adopted to deal with the standard wave equation.
Define \begin{align} t&=\xi+\eta,\\ x&=\xi-\eta, \end{align} whose inverse reads \begin{align} \xi&=\frac{t+x}{2},\\ \eta&=\frac{t-x}{2}. \end{align} With these notations, we have \begin{align} \frac{\partial}{\partial t}&=\frac{1}{2}\left(\frac{\partial}{\partial\xi}+\frac{\partial}{\partial\eta}\right),\\ \frac{\partial}{\partial x}&=\frac{1}{2}\left(\frac{\partial}{\partial\xi}-\frac{\partial}{\partial\eta}\right). \end{align} Thanks to this transform, the original equation $$ u_{tt}-u_{xx}-u_t-u_x=0 $$ is now equivalent to $$ u_{\xi\eta}-u_{\xi}=0, $$ whose general solution is obviously in view.
Firstly, $$ \frac{\partial}{\partial\eta}u_{\xi}-u_{\xi}=0 $$ is an ordinary differential equation, which can be re-expressed as $$ \frac{\partial}{\partial\eta}\left(e^{-\eta}u_{\xi}\right)=0. $$ Its general solution is $$ e^{-\eta}u_{\xi}=\Phi'(\xi)\iff u_{\xi}=e^{\eta}\Phi'(\xi). $$
Thereafter, integrate the last equation with respect to $\xi$, and $$ u=e^{\eta}\Phi(\xi)+\Psi(\eta). $$
This is the general solution you are looking for. Following the above steps, it is clear that we have not left out any possibility.
Finally, rewrite the expression by using $t$ and $x$, and the general solution reads $$ u(t,x)=\exp\left(\frac{t-x}{2}\right)\Phi\biggl(\frac{t+x}{2}\biggr)+\Psi\biggl(\frac{t-x}{2}\biggr). $$
Hope this could be helpful for you.
Edit: Alternative solution using the method of partial differential operator
Following what @UriaMor proposed in the question, define a partial differential operator \begin{align} P&=\partial_t^2-\partial_x^2-\partial_t-\partial_x\\ &=\left(\partial_t+\partial_x\right)\left(\partial_t-\partial_x-I\right). \end{align} As such, the original equation $Pu=0$ could be decomposed by two equations \begin{align} \left(\partial_t-\partial_x-I\right)u&=v,\\ \left(\partial_t+\partial_x\right)v&=0. \end{align} The general solution could then be obtained by solving these two equations using the method of characteristics.
Firstly, solve the second equation with respect to $v$. Note that $$ \frac{{\rm d}}{{\rm d}t}v(t,x_0+t)=\frac{\partial v}{\partial t}(t,x_0+t)+\frac{\partial v}{\partial x}(t,x_0+t)=0 $$ holds for all $x_0$. Therefore, $$ v(t,x_0+t)=v(0,x_0):=\Phi(x_0). $$ Replace $x_0+t$ by $x$ in this last equation, and we obtain $$ v(t,x)=\Phi(x-t). $$
Secondly, substitute this last result into the first equation with respect to $u$, i.e., $$ u_t(t,x)-u_x(t,x)-u(t,x)=v(t,x)=\Phi(x-t). $$ Similarly, observe that $$ \frac{\rm d}{{\rm d}t}u(t,x_0-t)=\frac{\partial u}{\partial t}(t,x_0-t)-\frac{\partial u}{\partial x}(t,x_0-t), $$ for which the equation above, when considered along the characteristics $\left(t,x\right)=\left(t,x_0-t\right)$, implies that $$ \frac{\rm d}{{\rm d}t}u(t,x_0-t)-u(t,x_0-t)=\Phi((x_0-t)-t)=\Phi(x_0-2t), $$ or equivalently, $$ \frac{\rm d}{{\rm d}t}\left[e^{-t}u(t,x_0-t)\right]=e^{-t}\Phi(x_0-2t). $$ Therefore, we obtain \begin{align} e^{-t}u(t,x_0-t)-u(0,x_0)&=\int_0^te^{-s}\Phi(x_0-2s){\rm d}s\\ &=e^{-x_0/2}\int_0^te^{(x_0-2s)/2}\Phi(x_0-2s){\rm d}s\\ &=-\frac{1}{2}e^{-x_0/2}\int_{s=0}^{s=t}e^{(x_0-2s)/2}\Phi(x_0-2s){\rm d}\left(x_0-2s\right). \end{align} Define $$ \Psi(x)=\int^xe^{s/2}\Phi(s){\rm d}s, $$ and the above equality reads $$ e^{-t}u(t,x_0-t)-u(0,x_0)=-\frac{1}{2}e^{-x_0/2}\left(\Psi(x_0-2t)-\Psi(x_0)\right), $$ or equivalently, \begin{align} u(t,x_0-t)&=e^tu(0,x_0)-\frac{1}{2}e^{t-x_0/2}\left(\Psi(x_0-2t)-\Psi(x_0)\right)\\ &=e^{t-x_0/2}\left[e^{x_0/2}u(0,x_0)-\frac{1}{2}\left(\Psi(x_0-2t)-\Psi(x_0)\right)\right]. \end{align} Define \begin{align} \phi(x)&=e^{x/2}u(0,x)+\frac{1}{2}\Psi(x),\\ \psi(x)&=-\frac{1}{2}e^{-x/2}\Psi(x), \end{align} and the above result goes that $$ u(t,x_0-t)=e^{t-x_0/2}\phi(x_0)+\psi(x_0-2t). $$ Finally, replace $x_0-t$ by $x$, and one eventually obtains $$ u(t,x)=\exp\left(\frac{t-x}{2}\right)\phi(x+t)+\psi(x-t), $$ which agrees with the result we have figured out previously.