First you need enchanted weapons to even touch them. And if you plan to use archers against them then the archers will need a way to see through invisibility. Otherwise just use a melee unit with enchanted weapons that can dish out some serious damage (say, elite halberdiers built in a city with an alchemist's guild, and maybe mithril or adamantium if you really want to go overkill). For dealing with them earlier in the game.... run.

Paladins are great against them. Just wait for those pesky elementals to kill themselves trying to hurt the paladins

Air elementals are a pain. They're invisible, so you need illusion immunity to see them unless they're next to you, or to launch missile attacks. They also fly, so you need some way to attack fliers to initiate attacks against them. Also, they hit pretty hard, so you need something can take quite a beating to defeat them. Oh, and they're intangible, so it takes magic weapons to hurt them without penalty.

Most racial high end units can beat air elementals, with some casualties. Heroes may not be such a great deal - air elementals have a disturbing tendency to gang up and gib heroes. They're not as bad that way as great wyrms, but they're still dangerous. If you have a really nasty and tough hero, though, he can probably take on a good sized group of air elementals.

Thanks folks, you've been a great help. :) Taking your lead re magical weapons, I attacked a nest of three with a stack of 9 Adamantium equipped champion slingers (when playing Halflings I never bother with swordsmen) and uning a "Thin Red Line" battle techique we won. Casualties were high but all survived although badly torn up. Cheers!