Lords of Madness introduces the director (137-8), a beholderkin much like a typical beholder except tentacles on its underside allow a director to enslave a creature with the type vermin, which then serves as the director's mount. A director's size is typically Large but advances by Hit Dice to Huge. While Gargantuan vermin are perfectly acceptable mounts for most Huge creatures (centipedes, scorpions, and spiders, O, my!), an advanced director already has a fly speed of 20 ft. (good).
I am of the opinion that a director's mount should be faster than the director and fly, but few Gargantuan vermin have fly speeds. For example, a Gargantuan vermin with a fly speed is the astral kraken (Planar Handbook 109), but it's too niche for my needs and its CR on the Material Plane excessive.
Is there a way to grant a vermin a fly speed while having it keep the vermin type? I just want rules-legal Gargantuan flying vermin. Y'know, like a winged Gargantuan monstrous scorpion. Is that so wrong?
I'd like the flying vermin to be actual critters, so a method that avoids spellcasting and magic items is preferred. While I know some dude could just cast the spell fly on the Gargantuan scorpion or the director could equip the Gargantuan scorpion with wings of flying, both are problematic. (The director can't itself cast spells, but I'd like it to function as a scout, so the flight method needs to be reusable and reliable, and I'd rather not an item like the wings of flying fall into the PCs' hands just yet.) Because the vermin must remain a vermin so the director can control it, I was thinking there must be a template, but thus far every template that would grant a vermin a fly speed also changes the vermin's type (for example, half-dragon to dragon, half-fiend to outsider). Not even the spell giant vermin is any help, affecting as it does only normal centipedes, scorpions, and spiders.
Official methods preferred to third-party and homebrew.