Is this something that FATE fixes? If so, I'll have to look into it!
On top of that, the way they rebalanced skill checks and AC ("bounded accuracy") makes the game feel a lot better. This [1] is a fantastic article specifically addressing those changes, if you're interested.
1: http://www.dandwiki.com/wiki/Understanding_Bounded_Accuracy_...
Examples:
FantasyCraft: D20 based, but drops the automatic success/failure rules, so at heroic levels you can have guaranteed success.
Shadowrun 3E: The maximum skill rank a starting character can have in any skill is 6, which translates to over 99.99% chance of success on "easy" difficulty checks and over 98% chance of success on "average" difficulty checks.
Earthdawn: Every 5 or 6 steps of a skill adds one more difficulty level that you can succeed automatically (starting at step 3, where you auto succeed at difficulty 1)
D&D Redbox:
No skill checks, Attacks succeed if the modified value is 20 or higher. So a level 1 Str 9 character can never hit AC -1. A level 1 Str 18 character needs only a 17 to hit any AC. These rules are different in later rulebooks when the THAC0 is introduced.
[edit] Checked my Expert rulebook, and found that the modified 20 always hits is just due to very low ACs not being represented in the Basic charts (In OD&D lower AC is harder to hit). The target number to hit goes up as AC goes down, but "sticks" at 20 for 5 points of AC. There is no special rule for auto hitting or missing with a natural 20 in OD&D. Note that monsters are quite good at hitting with the weakest monsters hitting about as well as a mid-level fighter with mundane equipment.
D&D 3E: Only attacks succeed/fail on a natural 20/1.
D&D 3.5E and Pathfinder: Attacks and saves succeed on natural 20/1
I don't own any AD&D rulebooks.