One easy solution to the tiering problem: Rather than split the teams into 3 tiers based on a sorted order, just randomize your input list so that the three groups will be approximately equal in quality. You would still have the problem of never playing with anyone in your tier as an ally, but at least you wouldn't have the big helping of rookies and hurting of veterans.
So rather than
You might have lists like
On average, they will even out to have the same number of powerhouse teams.
The whole tiering thing seems to be a wierd solution to a problem that didn't really exist anyway. Now instead of a few teams sometimes legitametely complaining that they got a bad deal in the pairings, you've got a whole group (the veteran teams) who get a bad deal, and they can prove it.