So really what is the difference if people choose to max their skills out in 4e as opposed to 3.5? How has any of this actually been solved, except through player agreement or DM fiat (same as in 3.5) in 4e?
It isn't as big of a problem. Keep in mind that the difference between +16 and +7 is still such that a DC 20 is an appropriate challenge for both of them. The +16 guy is likely going to be the guy doing it, however.
I don't have a problem with specialists. This is exactly the difference between characters in 4e. In 3e, the math works out such that there are specialists(those with race, feat, class, other modifiers or a high stat with max ranks), people who are good at the skill(anyone who just took max ranks with a low stat modifier and no other bonuses), and people who can't use the skill(anyone with less than 75% of the max ranks in the skill). In 4e, there are specialists(trained while stacking feat, race, backgrounds), people who are good at the skill(trained in it and a high stat modifier), people who are ok at the skill(trained in it with a bad stat modifier, or not trained in it with a good stat modifier), and people who are poor at it(anyone not trained in it with a bad stat modifier).
Even with your example, if you have a DC 20 challenge, the guy with +16 it going to fail some of the time and the guy with +1 due to a 12 in the stat and no training is going to succeed some of the time. That's the key. You never run into a situation where you CAN'T set a DC without guaranteeing success or preventing anyone but the specialist from contributing(before anyone tries it, I am aware that at the absolute maximum difference it is possible to make a DC that breaks it. But you have to REALLY work at it).
The thing is, at 1st level, if I set a DC of 15, I know that anyone who super specializes will succeed automatically(+14-16). Anyone who trains in the skill and is good at it(+10-12) will succeed most of the time. Anyone who simply trains it in or has a good stat with no training(+5-7) succeeds a lot of the time, with a significant chance of failure, anyone who doesn't train at all in it(+0-2) has a bigger chance to fail than they do to succeed, but a real chance of succeeding.
This creates an fairly accurate way of setting DCs based on how you want a group to do. DC 20 is the sort of check that the average group(one without a specialist) succeeds roughly 55% of the time, a poor group succeeds 30% of the time, and an exceptional group succeeds 80% of the time. It's the "hard" check at 1st level. You can easily adjust this up and down. DC 10 for "easy" checks, DC 15 for "moderate" checks, DC 25 for "nearly impossible" tasks. This holds true all the way through level 30. Where the highest bonus is +31 and the lowest is +15. If you set a DC at 20 and the specialist is away from the party, not showing up for the session, or if you have no idea if the group has a specialist....then the group still has a chance of succeeding.
As a side note, before anyone points out that the Skill Challenge DCs are lower than these, I've gotten word from the people at WOTC that the reason the DCs are so low in the errata'd version is because they assume that PCs will often be forced to roll their low skills. If you allow the PCs to choose their own skills every time in a skill challenge, it's recommended that you up the DCs at least 5 points.
This is in contrast to the 3e method, which could range from -2 through +55(or slightly higher) at level 20. So, if you set the DC at 60 so that the specialist has an 80% chance and he is unable to make the check, the guy with +30 due to "only" having max ranks, a 20 in the appropriate stat and a racial bonus can't possibly succeed.
In summary, specialists aren't the problem. The gap between specialists and the lowest person in the group is a problem. As a side note, ranks would work fine house ruled into 4e as long as the most ranks you could put in was 5 and you kept the +1/2 level, and there was no "trained" skills.