Not the first one, and I don’t think I beat the second one, but I did beat the third one without cheating. Really loved the last mission. The big demon was literally two steps away from getting into the big magic circle that would’ve ended the game before the time ran out and I won.
Never finished all the Zerg missions in StarCraft, either, come to think of it, but I did finish the Terran and Protoss campaigns.
Oh, yes…Warcraft needs to be cheated at. >_>
I cheat a lot less at II than III, though - the one cheat I use all the time in III (the one that relaxes the food restrictions) isn’t needed in II.
Awesome game, but it seriously needed a save/restore option, or at least passwords. I did eventually beat it on an emulator where I could save, but it took me 20 or 30 hours of gameplay.
But the crab boss was the one that stopped you? As long as you have a decent gun, he’s easier than most of the regular monsters. Stand at the bottom of the screen. Face up. Hold down fire button. Wait. Collect dive module. Everything he shoots at you, you can destroy by shooting it, so he literally can’t hurt you.
More votes from me for Half-Life and Myst.
Reaching back (if 10 years isn’t far back enough), Impossible Mission on my old C=64. No matter how good I got at it, I could never get all the puzzle pieces and figure the damn thing out before the time ran out.
I solved most of the Infocom games, I loved them and the text-based MUDs that flourished from about 1990 to 1997. Never did solve Suspended though.
I finished every Ultima game through Ultima IV, then got fed up with the damn ethical impositions. Ultima III was my favorite. You could fire ship cannons on shorebound monsters, sack entire towns, even kill Lord British if you had the right stuff, and still finish the game. And the ending was kinda cool, when you discovered what the big baddie really was…
Ultima II (excuse me, ][) had that awesome element of going into space though.
Malak’s actually fairly easy to beat if you go about it right. Conserve your Force powers: slap on Burst Of Speed and Force Immunity, and use health packs and stims to boost strength and stamina, replenishing as necessary - Heal is tempting, but drains your mojo too fast.
Use the best shields you have - the Verpine Prototype Shield, which you can buy off the shady Rodian bartender/arms dealer on Korriban is expensive, but the toughest - stock up! {the Echani Duelling Shield also good} - and keep them topped up.
If you have Demolition skills, seed the narrow walkways with mines.
Right, to battle: if he had a chin it would be glass, and he can’t take a good hit. Whack him a couple of times - I found a Master Flurry/Critical Strike combo good - and then he’ll break into another gloat and dash off to suck the mojo out of his captive Jedi. Now’s your chance to…
KILL THE JEDI. That way he can’t keep replenishing his vitality, and you won’t attract any Dark Side penalties. You’ll need Burst Of Speed here: dash around the various tanks, and use pretty much any ranged power to kill them - Throw Lightsabre works well, but Destroy Droid and Force Lightning are good - if you’re Dark Side, Drain Life is especially good. You’ll probably need to boost your health after you’ve killed each one, but right now you’re not one on one with Malak, so you won’t take too many hits.
OK, once the Jedi are dead, you can go mano a mano with Malak. It’s probably easier to fight him at a distance - just keep running away and stop occasionally to fling your lightsabre at him, and that’ll whittle him down: just remember to keep topping up your stims, shields, and Force Immunity as needed, and he can’t do too much harm. I prefer slugging it out with lightsabres, myself - the guy really can’t take a good hit, and once he’s unable to replenish his mojo you’re probably more than a match for him, especially if you’re a Jedi Guardian.
Which makes that monolouging he does at the beginning of the fight even more pathetic.
Ah, remembered some more:
Mario Party 5 - Was a rental.
Pikmin - Not my Gamecube.
Final Fantasy Crystal Chronicles - Ditto. Also didn’t do a good job of leveling my characters, and they kept dying inappropriately.
Luigi’s Mansion - Ditto. This friend also didn’t have any space left on his memory card.
I believe that you are correct (but why play at anything but the naughtiest level? 
) I think it also came with a 3D comic book and glasses. I bought “The Lost Treasures of Infocom”, Volumes I and II some time ago. Their copy protection was usually to include some clue in the supplementary materials that came in the package, which I liked a lot.
I got through Zork, and most of the way (I think) through Zork II. Zork III was supposed to be a different sort of puzzle with different goals, so I have no idea how close I came to finishing. Not very close, I think. I finished Zork:Nemesis; although it doesn’t have the humor of the Zork series, it is (to my mind) more satisfying in its conclusion.
I’d highly recommend Dark Fall (the first one). There are a number of problems to solve, but it is non-linear, so you can work your way through at your own speed. Be prepared to take lots of notes, though.
I love adventure games, whether graphic or text. It isn’t unusual for me to have several in various stages of completion on my computer. A brain cramp in one just means I switch back to another.
I am pretty much doomed to not complete video games – though I did complete the original Prince of Persia (while a student) and Diablo I & II they are the only games I’ve ever completed.
The games I WISH I’d been able to finish, but just couldn’t include:
Mechwarrior 2 & 3
Thief
And the aforementioned American McGee’s Alice
All of which seemed interesting, but more time than I cared to put into them.
Thinking way back to my old Commodore 64 days…
Suspended: The box had this white plastic mask on the front, which was meant to represent you, as the player (in suspended animation), who remotely controlled five robots in a partially nonfunctional research station. I could not for the life of me figure out what I was supposed to do.
More recently:
Viewtiful Joe: I suspect I just lack the patience to train in the fine motor memory required to defeat the last boss (according to the walkthrough, a fairly precise sequence of maneuvers that need to be performed repeatedly).
Metroid Prime: I kind of lost interest halfway through, again when I couldn’t manage to perform three perfectly-timed explosions to lift the rollerball form up to an open pipe overhead.
Well, remember the fight on the Leviathan: ten minutes of boating about how tough he is and how feeble you are, and how he’s going to finish you once and for all to show everyone who’s the man, all those warnings about how “you cannot stand against him”, and what happens? A couple of good hits and he runs away. Twice. If the game had played fair and Bastila hadn’t showed up, I would have had him then and there. He’s a big girl’s blouse who hides behind his toys.
No wonder he Fired on your ship trying to kill you when you were Revan.
I’d like to nominate Malak for “Pussiest Final Boss in the universe” award.
These games I haven’t been able to finish without cheating:
Starcraft: I finished the terran and zerg campaigns ok but the protoss are just too expensive for me to finish without cheating, plus I really wanted to see how it ended.
Doom/2: I’m too trigger happy, actually I’m kill-crazed and bent on destruction. That’s not a good thing when you have limited ammo.
Age of Mythology: I wanted to build the biggest monster army I could and that means having no villagers.
These I didn’t finish “like a man”:
**
Diablo 2**: I never finished it in Hell difficulty, I only got as far as a few feet from the Rouge Sister’s camp before losing patience. Damn those immune monsters and my crappy assassin build!
Rome: Total War: I did finish it in the middle difficulty setting once but then I got this great mod for it called Rome: Total Realism, and because this mod stretches out the game from 180 B.C. to 180 A.D. and probably has five times the original amount of provinces, I just don’t have the years it takes to finish it now.
These I just plain didn’t finish:
Morrowind: Too open-ended for me. Don’t play a game with next to no story line when you just finished BG2.
Black and White: Lost interest. I want to be a god not some damn chimp’s babysitter.
Prince of Persia (the first one): Just one hour to finish it, are you nuts?!
Unreal Tournament 2005: I just can’t finish Assault Ladder, but why even bother since even if you finish it it doesn’t really unlock anything.
That’s all I can think of. I’m currently playing Dawn of War, I wonder what category that one will end up in.