Well i can't tell you a solution for this, maybe the best for the masses would be to take away those additional houses players own, and only leave them the largest one, or the house with the most items inside.
My Server is very young and doesnt have that problem to begin with so i don't know how bad it is for others. Last time i checked a few days ago, Goblet had 16 free plots available, i also know a lot of people dont even have enough Gil on my server to afford a small one, although 3-4 million really isnt that much.
Twintania always has free plots.