So far:
A. Last-time's method. All RNG but no one can border a teammate. That got a little hairy with countries like Genoa and what it meant to be "bordering". Somebody (non-player) generated the teams and then DM'd each of us who our teammates were. There are other rules we could implement or we could better define "bordering".
B. If we do unknown teams, I think it would be worth it to consider truly random teams; while it probably won't end up balanced, this game is for fun anyhow. A true mystery.
C. We determine 9 "captains" before the game starts, and once we get in-game, those captains draft or bid on their teammates. Further details to be decided if we pick this one; we have a lot of ways to do this.
D. We sort out which countries go into which set of teams before the game starts, and go in with random country assignment.
E. Drano's idea. We choose the 9 captains(by rank or by election). After the game starts, all captains submit a ranked list of three picks to a third-party to decide what they get for the first round of bidding. If possible, they are all assigned their first choice. If not, multiple picks crash, they get second, or third. If someone end up with nothing, then this round is redone. We do it for three times. Each round, every captain only knows which countries are still available, while others know nothing.
F. MagicalSand's idea and Lief_Syverson's supplement. Each team is two pairs that do not connect with each other or sandwich another pair. Details to be discussed.