Is secure remote snap possible?
Yup, should be possible.  Look at multiparty secure computation protocols.

In particular, you might want to look at secure protocols for private set intersection.  $P_1$ and $P_2$ can use such a protocol to find the individuals that are in the intersection of a set known to $P_1$ and a set known to $P_2$.  Then, they can let $S$ know whether there is any intersection and what the correspondence between IDs is

Specifically: $P_1$ has a set of individuals ($f_1^{-1}(a)$), and $P_2$ has another set ($f_2^{-1}(b)$); now a private set intersection protocol lets us check whether these sets have any elements in common, without revealing anything else about the sets.  In such a protocol, the set of individuals never leaves $P_1$ or $P_2$, but we still have a way to learn whether $P_1$'s set $P_1$ has any overlap with $P_2$'s set.  The details are, well, detailed, but if you are interested, look up any reference on private set intersection.

This approach scales beyond pairwise comparison of individual IDs; if the server has a set of IDs on $P_1$ and a set of IDs on $P_2$, you can use this approach to find whether there is any overlap between these sets and if so, what the correspondence is between the IDs.