Personally, I favour the Warmachine approach:
All players are allowed to bring two lists, before they game they get a few minutes to study their opponent's two lists, and then secretly choose one of their two lists to play. Both players reveal their chosen list at the same time, set up the game and deploy.
Serves the same prupose as a sideboard without the hassle of on-the-spot point cost calculations and stuff. Also opens up a bunch of interesting strategies: Say, a normal all-comers list and an anti-flyer list. Or a list designed to fight light infantry armies (Orks, Guard, Eldar, Tyranids, etc.) and one designed to counter heavy infantry armies (Marines, Grey Knights). Or an Eldar Iyanden list full of Wraith-stuff and a non-wraith list for the few games you run into Dark Eldar poison or IG pieplate spam. Or just ignore the counter-game and bring two different lists for some diversity, say a Green Tide and a Cult of Speed Ork Biker list. And watch your opponent squirm as he tries to guess which one you'll be using and which of his makes for the best counter - then when he's selected his list put out a die and declare "on 1-3 it's bikers".
Of course, none of that really counters the issue of codex imbalance, which is the real issue both here and with all claims that allies unbalance the game.