Battletoads

Phantom Brave for PS2... one of the most difficult games I've played.
PS: I didn't find Mafia to be a hard game...

Apparently not. I cant remember most of it, its been a long time since I played it last. But I do remember the garage scent which I had to do (without exaggeration) at least 12 times. Until I memorised exactly where every single enemy was and was able to portion out the ammunition right I got wasted every single time. The other example is the scene in the back of the truck, the one where you protect the boose with thugs after you (or something). There unless I was able to remember where every consecutive truck full of cannon fodder was going to come from I was wasted every single time.
Oh and it is pretty biased of you to assume right off the bat that I must have been playing the game a certain way if I wasn't enjoying it. I wasn't really. Not in the way you describe anyways. Besides wouldn't be much stunt driving involved here in the first place considering how the cars handle in the game.

Nah mate, the only reason I mentioned playing it like GTA3 was because they were out around the same time and most of the trouble I remember helping people with on forums at the time was in getting them to realise they're fairly different games and benefit from being played differently.
That garage mission (which I think contained a reference to bill gates) could be a real bitch though, I had to re-do that one a fair number of times myself. I never ran low on ammunition though, suppose its one advantage of having so many enemies, a few quick kills and you've got a few more mags of ammo.
Damnit, now I want to play Mafia again...

I don't know why people say megaman is so hard. I always found those games to be the perfect middle ground. If you want something more challenging but not entirely unfair, try Contra 3 for SNES.
Try Risky Woods for PC. That game seems just unfair. I've mentioned Ikari Warriors 1 for NES, which I loved when I was small. See if you can find a cart or ROM and give it a try - it's psychotic.

The problem with mafia is that it combines realism with fiction in a bit wrong way.
Bullets are deadly. two, three shots and you are dead.
but you still have to kill dozens of people, no less than in GTA or other game.
I mean: how many gangsters during one heist kill single handy 30 people?
That made game incredibly hard for me forcing me to replay most mission at least a couple of times just so I know what to expect.
"Where the gangsters go when they die?
They don't go to Heaven where angles fly!"

What? I've driven a 20 year old trailer that maneuvered better on a dirt road than the average car in GTA 4 on the in game asphalt. The driving in that game does not feel realistic. At least the ground in the game doesn't...

Mafia isn't that hard? Sure, you have to replay some levels pretty extensively before you get the hang of them, but they are among the few. Most missions you beat in 1-5 tries.
And what would define a hard videogame? There are two main "types":
- A game that is hard by design
- A game that is hard by design error
Such as; Contra is hard by design (but a very good game nonetheless). With good practice and many hours of play you became very good at it, to the point where you could beat the game almost every time.
Paperboy is hard by design error, because they added so much shit to avoid it became virtually impossible, and wasn't a fun game anymore. Just try getting to Friday in Paperboy 1. It's impossible for all but the completely fanatical, no matter how much you play it. It was hard when I tried using an emulator with slowdowns.
I vote we only recognize good games that are hard.

First of all, that's what she said.
Secondly, I actually think cheap games are more interesting to talk about just because of the fury they evoke. But regardless of games' extreme difficulty due to intentional or flawed design, it doesn't change the way you want to break things or punch the designer's face in if you ever meet them in person.

The Adventures of Bayou Billy for the NES. I think playing it actually qualifies as some sort of punishment.

At the Moment Jade Empire. Clunky controls/camera and 3 hit combos that take away half your health is infuriatingly frustrating.

I'm still stuck on Level 2 of the original Thief game after 8 years of playing it.

Speaking of car games, I'd like to mention Need For Speed: Porsche Unleashed/Unlimited's career mode.
This is going from memory a bit, but I do remember the agony of driving through dense urban traffic at high speeds to reach my goal within the time limit, and then being told I failed because I scratched the car.

And now I'm on Level 3 :D