Despite everything it still takes a while to get into a match.
Technical difficulties aside, it simply is a problem with the lower userbase when compared to, say, Warcraft III.
So, when few users are online, it will take longer to get into a game, simply because the few users online ARE already in a game.
With more users online, there will not be a problem like that ... the more people are playing, the more games will end soon, freeing players for the next matchup.
This is a fact and a key to the solution: Shorten the length of a match when few people are online.
Stardock should have plenty of statistical data by now. Analyze them for the match conditions that produce short matches and emphasize those when creating new skirmish or pantheon games.
I don't have that data but I have my guesses:
* Fortress games are shorter than conquest games
* Domination games can be time controlled especially easily by tweaking the domination counter.
* Slaughter games with many people probably don't last long either.
And then there's always the option of making new game modes, like:
* Time Attack: Human Team must defeat AI team within a certain time limit. Double Favor for best player, half for the rest.
* Undefended: Conquest game, but no base defenses. Reinforcements spawn twice as fast, though.
Adds variety and decreases wait time by lowering match lenght.