Elliptic Regularity via a Pseudodifferential Parametrix