Lakitus in level 2-5 of Yoshi's Island prevented me from getting 100% in that level for 7 years. I hate them and I want to destroy every last one of them. But then you get hurt 60% of the time when you try and kill them, and they taunt you from their stupid smiling clouds...

Ice Keese.

Paper Mario, the Dizzy Koopa (?)

The enemy can put your character into a cycle of endless incapacity, the effect is like being skipped in UNO constantly. It's not hard to see how this is problematic, especially when the issue is compounded (in the N64 version) by partners who can't use items to heal off the damage.

FireBrand in Ghosts 'n Goblins for the NES/Arcade. Their patterns are highly unpredictable...
And you can't run away or else they'll swoop down and trample you until you're medieval toast!

You're not a man unless you've beaten Ghosts 'n Goblins. It will put pixel hair on your chest!

Pipis in Megaman II. God I hate them. Especially in the Airman level.

Mario Kart or any other racing game- Rubber banding AI

Super Mario: Hammer Bros.
Zelda: Blue Soldiers
Metroid: what else?

As much as I adore Sonic the Hedgehog 2, pretty much every enemy in Metropolis Zone annoys the crap out of me. The mantis-bots especially.

EDIT: These jerks -

In most cases, anything that has wings and flies are a pain to deal with.
Among other things like Sonic 2 Slicers, and most recently:

I hate these!

Them eagles from the original Ninja Gaiden on NES

Flying Medusa Heads from Castlevania. D: D: D:

Metal Slimes from the original Dragon Warrior / Dragon Quest

Tempura Wizards from Kid Icarus Uprising, they only got me once (as in ate), remove my avoiding abilities, then go in for a one hit!? What a pain.

Yeah. If you see one of those, you might as well come to realize you are not keeping your rings. They're all like "come a little closer...I'm not going to throw anything at you", then you jump in for the kill and the next thing you hear is all your rings bouncing around.

From Super Mario: Pretty much anything and everything that debuted in the Lost Levels (walking Hammer Bros., flying Bloopers, Poison Mushrooms, Backwards Warp Zones...need I say more?). That last one in particular.......oh man was that ANNOYING. Oh and of course the "Leaf/Clay Boats" from Mario Sunshine.

Zelda? Blue Wizzrobes, Blue Darknuts, Like Likes, and Bubbles, all from the original NES game. By themselves, they're among the most annoying enemies in Zelda ever. Together in one room? Brutal. Also, those blue flying Phoenix Knights from Zelda II.

Can't forget the Eggplant Wizards and Thieves from Kid Icarus, either.

Medusa heads.

Medusa heads and fleamen from Castlevania. You want to platform successfully? Nope. Fleaman knocks you off. You're jumping? How about a Medusa head petrifies you in mid-air. The Clock Tower stages in these games were horrible. Not only do they have death spikes and moving platforms, but they also have enemies trying to knock you off those platforms.

You can commit suicide in the pit placed for you near the pipe or timed out to avoid it.

I've never gotten what's so annoying about the Medusa heads in Castlevania.. They go in a pattern, which makes them easy to kill, at least to me..

The birds in Ninja Gaiden, the Hammer Bros. in Super Mario Bros. and the flying enemies in the Castlevania games.