Let $M$ be a smooth manifold, like $\mathbb{R}^n$ for instance. The existence of a parametrix for an operator $P$ on $C^\infty(M)$ in any reasonable pseudodifferential calculus implies that $P$ is hypoelliptic. Is there a converse to this statement?

The converse would have to take place in some very general setting that encompasses all possible pseudodifferential calculi. Here's how I'd like to phrase it...

An operator $P$ on $C^\infty(M)$ is "very regular" if its Schwartz kernel has the following two properties:

(1) $p$ is properly supported and semiregular in both variables, ie, $p \in (C^\infty(M) \hat\otimes \mathcal{E}'(M)) \cap (\mathcal{E}'(M) \hat\otimes C^\infty(M))$,

(2) $p$ is equal to a smooth function off the diagonal.

The first condition means $P$ maps each of $C_c^\infty(M)$, $C^\infty(M)$, $\mathcal{E}'(M)$ and $\mathcal{D}'(M)$ to itself. The second means $P$ is pseudo-local.

Suppose a very regular operator $P$ is hypoelliptic, in the sense that every preimage of a smooth function is smooth. Does this mean that there is a very regular $Q$ which is a parametrix in the sense that $PQ-I$ and $QP-I$ are smoothing operators?