Potential solution to ensure both random but equal matchups:

With five players and 3 potential matchups per round, there are 15 potential pairings total:

1. Brian-Derek
2. Brian-Kyle
3. Brian-Marc
4. Brian-Mike
5. Brian-Stu
6. Derek-Kyle
7. Derek-Marc
8. Derek-Mike
9. Derek-Stu
10. Kyle-Marc
11. Kyle-Mike
12. Kyle-Stu
13. Marc-Mike
14. Marc-Stu
15. Mike-Stu

I print out cards with each pairing, we fold them, put them into a hat, bowl...whatever, and we pull them randomly. Since there will be a total of 10 rounds, with 3 pairings per round, or 30 pairings total, I'll print out two sets of the above pairings, drop them into the hat and once the pairing is removed from the hat, that's the pairing from it's discarded (recycled responsibly, of course). For the second set of prints I will reverse the order of the names in the pairing (i.e in the second set, 'Stu-Mike', 'Stu-Marc', etc...

The name that appears first in the pairing will play first.

Think this will ensure fairness in that:

• we all face each other the same amount of times
• the order in which we have to play a song first is equal and fair for each matchup
  
• when we face each other is completely random, so it introduces element of surprise that will require strategy, decisions as to when to bring out (what you perceive to be) the big trump card/song, when to play a slower song, etc. For example, Brian and I could face each other in rounds 1 and 2 (and then never again) or we could face each other in the first round but not again until the tenth round. The strategy then shifts--do I save a particular song or year for a particular opponent. If Brian uses up 2 songs from 1978 in his first two rounds and then has to play a song from 2005 (can't play the same year three rounds in a row, see previous posted rule, assume we agree on) in the third round, he's not going to know who he'll face in that third round until we draw.

Hope you like this idea. I will do all the printing and prep to bring this stuff to the session. Thinking if it works, we can always do it again next year with different year pairings!