I took a stab at this exact scenario years ago (1999?) and came to roughly the same conclusion. I ultimately decided to treat it as a travelling salesman proble

I took a stab at this exact scenario years ago (1999?) and came to roughly the same conclusion. I ultimately decided to treat it as a travelling salesman problem where the distances between nodes (people) were weighted based on how recently they had matched with each node in the past. This ultimately led me to create a TSP solving library that implemented a bunch of the known heuristic algorithms to approximate the solution. Worked out pretty well in the end and learned lots while I was at it.