Algorithm to find pairs
It seems that you are looking for a maximum matching in a graph where vertices represent people and an (undirected) edge $(u,v)$ means that $u$ and $v$ have not met before.
This problem can be solved in time $O(n^{1/2} \cdot m) = O(n^\frac{5}{3})$, where $n$ is the number of people and $m$ is the number of pairs of people that have not yet met.