I have seen way too many questionable moves in which a player seems to act against their own best interest to ensure victory for someone else, only to examine their play histories and see that they have been partners in other games. Secret alliances are pretty much impossible to prove, but worst of all they are not apparent until the game is out of reach.
I don't want to ban or limit people playing together, all I want is the following chat notification added when the game is initialized:
"Players XXXX and YYYY have been partnered together in previous games."
Obviously the message only appears of they are opponents, not partners.
So that's all I want, a message. It isn't especially accusatory, it doesn't effect the actual game, and it doesn't constitute evidence proving anything. All it does is inform the other players in the match that these players have a prior history, and maybe they should watch the game more carefully.