Is this something that FATE fixes? If so, I'll have to look into it!
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.
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)