Since freebies don't like getting stomped on by paid players, and paid players want to play other paid players (or else they have major self esteem issues), why not do this:
Simply implement a boolean variable whether or not a player has spent money on the game. If he has, he'll only get matched up with other players who've spent money. In the meantime, the freeloaders will only get matched up with other freeloaders and that way not run into any situations that frustrate them simply because they didn't pay.
This way, we segregate and avoid frustration.
Of course, this begs the question as to what happens when a player spends a little bit and gets matched up against someone for whom money is no object. Sucks for the little spender then. Shouldn't have spent to begin with. The idea of more precise matching by spending levels is also an option, but not with the community as tiny as it is.

