One of the Trope Namers here is Castlevania, which had bats that continually respawned from the side of the screen you were facing, usually during sequences in which you were trying to jump from one moving platform to another. The crows are also like this.
The game collection Retro Game Challenge paid homage to Castlevania's bats in the platformer Robot Ninja Haggle Man 3 with birds that would suddenly fly across the screen, often (or perhaps especially) at inopportune moments. They featured a lovely knock-back effect that would invariably send you into one of the game's many bottomless pits.
Dracula in Order of Ecclesia actually uses bats in one of his attacks; which is the most annoying attack he has, and trying to escape means he will fry you with a pillar of fire.
Castlevania also has Imps, tiny flying critters that move erratically, trying to stay out of your weapon's range, and when you're busy trying to take one of them down, another will move in from in behind and jab you in the head from behind with their spear, taking control of your body and then proceed to either make your character attack repeatedly (which seriously sucks if you had any depletable items equipped) or walk constantly in one direction without accepting any other input. Once that happens, you're completely helpless until they've had their fun. That is, unless one of their friends doesn't immediately re-control you the second you're freed. If you get caught with other enemies or spikes in the room, you're pretty much dead.
While we're on the subject of tiny flying monsters that come out of nowhere to bother you while you're trying to platform, there's the Medusa Heads, which, like bats, tend to respawn constantly. Especially annoying in almost any version of the Clock Tower, where a combination of moving platforms and tight spaces (and, in Symphony of the Night, a special room only unlockable by hitting several oddly-placed gears about a dozen times apiece) makes swarms of things that petrify you very frustrating indeed. Unlike the bats, Medusa Heads don't move in straight lines: instead, they take a sort of sinusoidal path across the screen, making it much harder to hit them before they reach your location. Also, in many games, the bats will spawn in specific locations when you enter a room, and there's a limited number of them. However, no matter what game you are playing, Medusa Heads will always spawn infinitely from off the side of the screen.
Aside from the petrification, the flying skeletons have a similar movement pattern, except they are much larger and sometimes take more than one hit to kill. Thankfully, they spawn less often.
Hard modes in any post-Symphony title more often not turn Goddamned Bats into Demonic Spiders. See that bat that used to do only 1 damage? Well, now he does at least 60.
Circle of the Moon brings us the Bloody Sword enemy type: Ignores terrain, small and difficult to hit, often takes more than one hit to kill, does high damage on contact, and will relentlessly hound you until you either leave the room or die. What's worse, they share this territory with honorable mention Goddamned Bats the marionettes, which will curse you, preventing you from fighting back in any way shape or form (except sliding) for about 45 seconds. At least they don't respawn.
The Dracula X Chronicles (a remake of Castlevania: Rondo of Blood) took the basic bone-throwing skeleton, and put them on many platforms just above. You have to fight enemies on your floor while dodging bones from above, and are unable to fight back till you can get up to their level. The original Castlevania also did this.
Flea Men. The move fast and jump around like maniacs, apparently just to drive you crazy while you're trying to fight more powerful enemies. The Rippers are much the same, except they throw knives. A lot. As bad, if not worse, are the ones that carry axes or ride that skeleton dragon and chase you across the room. And in some games you have fleamen riding eagles, who fly around very erratically and just won't leave until you kill them. And they just keep coming— you can easily be swarmed by about 4 or 5 of them if you don't kill them fast. It doesn't sound like much, but even two is enough to piss you off.
A notable trend in Castlevania is annoying flying enemies. The birds, bats, medusa heads, fleamen riding eagles, the imps, the winged skeletons, they all fly. This is because either they interrupt your jumps, or because they're a nightmare to try to hit, and so they persistently annoy you.
Oddly enough the bats in Castlevania: Lords of Shadow are completely harmless. The real Goddamned Bats in this game are goblins and chupacabras. The goblins are ridiculously easy to kill but can still be a real hassle thanks to their numbers and grenades. Chupacabras don't show up too often but seem to exist for no other reason than to harass you and make levels longer by stealing all of your magical items.