Halo 3 multiplayer had this solved by maintaining a dynamic rating of the players so that it could match skill levels when random matches were made.