Hmm... no one has mention Shinobi or Nightshade.
I never played Shinobi, myself, because I heard it was even harder than Nightshade. But the final levels of Nightshade were the hardest levels I've ever played. What really made it hard was that the cutscene that happened when you chained killed. It would freeze your character in place, show some type of pose type cutscene, then drop you back into the game. Which more often than not, would cause you to fall into a bottomless pit. And being that this was a PS2 game there were no saves, only checkpoints. So, whenever you died. You started over. Great fun that was.
OH. Did I forget to mention that the final few levels had no floors. Hardest game I've ever played.... and completed. And then there was a car platforming jump battle and a submarine platforming jump battle that were both major tests of patience. God Hand, Bayonetta's Non-Stop Infinite Climax, and DMC3 US original (normal=hard) are both child's play, compared to that game.
http://www.gamespot.com/nightshade/
I recall one mission in Mafia II that had me pulling out my hair. I vaguely remember having to follow a car, and the car kept on getting stuck in traffic, which would cause the game to blame me and say I failed. I didn't fail, your stupid AI failed. I do love that coke-a-cola and rum song that's in that game, though.....