I you treat a pair as a one-direction edge, and only match when you have an edge in both directions, then you could add text message verification to prevent people from both impersonating others and extracting additional information out of the service. It would be reasonably trivial then to notify clients when a new match comes in.

This approach seems to require that you trust the server.