10 k players each day means 3333 games each day, which makes 139 per hour.
Assuming it takes 1 minute to shuffle them together and 2 minutes to play, that is 3 minutes per game, making 417 game minutes needed every hour (with 60 minutes) ... so with that assumption there are alsways (on average over the day) 7 games running at the same time.
And again, 7 parallel games mean 21 players to be shuffled ... so as I see it, Naike's idea together with my little extra database table would not mean too much waiting time, if playing with the last 5-6 opponent is excluded (if the table contains 6, there are still 14 candidates not in that table).
Maybe the cheaters will meet again every 4th or 5th game that way ... that at least takes some of their motivation.
However, listening to HMR, the assumption of 10k players sounds very ... hopeful. Also there are times with lower player load, when that little table might better be switched off (until the cheaters find out and/or better ideas came up).