The problem is that unless you have a "New Game+" option, which in many cases you don't (most prominant in RPGs), it'd be difficult to make it so the game knows when it's been played through one or more times.
Say you play Gears of War. Now, I'm not a fan of those types of games so I can't say I've played it and thus I don't know if it has an option to save after completing the game to make a New Game+ option, but let's assume for a moment that it doesn't. You play it, complete it and even decide to keep the final save (just before the final boss, let's say). If you then decide a few months later that you want to play it through again, you start up a new game. Now, the game doesn't know that you've completed the game beforehand. It's only knowledge of a previous playthrough is the save that stops right before the final boss. So as far as it's concerned, you haven't completed the game and thus won't give you the option of skipping the tutorial.
Again, refering to a previous post of mine, it's a problem that developers have to make. Boring tutorial or risk bad press from those who choose to skip it.
EDIT: Totally didn't read the rest of your post on the whole Gears of War thing xD
Still, not all games use an achievement system so while it might work for Gears of War and maybe Call of Duty and such, it wouldn't work for every game. Add to that there's a chance of achievements either being lost (your console hard-drive crashing) or not being gained in the case of multiplayer (just as you do something, your wireless or the game server crashes and you don't gain the achievement). The latter of which has happened to me a number of times on Fallout: New Vegas, though we won't go there, what with the current hatred for F3 going on anyway...