the good news is - the banshee is really an exception. there are no other creatures in the world that are totally immune to physical damage. you'll make that mistake once, and remember it the next time just bring a champ with a damage spell or some weapon with bonus elemental damage - or build a few guys with fire or frost staves or other enchanted weapons. if you bring mage to counterspell her wail, she's harmless.
there are other critters that are immune to certain types of damage (magic in general, or fire/frost/lightning/poison), but that's easy to overcome since most of your trained troops will deal non-magical, non-elemental damage anyway.