The hardest game I can recall is Gradius V. I'm proud to say I managed to win it on Normal before I got infinite continues (but just barely—it took nineteen).
That game's Very Easy mode, by the way: most inaccurate name for a difficulty level ever. By far.