Bar none the hardest boss I've ever beaten is this guy: Kaizo Mario 3 - Bowser. The moment I saw this fight, I instantly got my hands on the game, put a savestate before the boss (not gonna bother with the rest of the game, it's too freaking hard) and spent the next... year and a half or so repeatedly trying the boss before I eventually managed to beat him. He's like a bullet hell boss, except random and with Mario physics, which is a recipe for disaster. But since your deaths are always your own fault it was pretty damn fun, and eventually you just get good enough to beat him. And it was smurfing magical.

Honorable mentions to Yukari Yakumo (Touhou 7: Perfect Cherry Blossom) and a couple of challenge battles I did in Final Fantasy X-2 and XII.