What are some good examples of partial combinatory algebras (a.k.a. Schoenfinkel algebras) with surjective pairing? I mean this in the sense that, if $\mathsf{D}$ is the pairing combinator and $\pi_0,\pi_1$ the projection combinators, then $\mathsf{D}(\pi_0x)(\pi_1x)=x$ for all $x$. Especially interesting would be examples where application is strictly partial, so that the PCA is not just a C-monoid.
(I'm not sure what some better tags are for this, so I'm open to suggestions on that front.)