I was about to suggest something similar with Lesser Planar Ally, but your way is considerably more efficient.
From the SRD: try Xorn for their Earthglide (Burrow through anything);
Janni for Telepathy, elemental endurance, PLANE SHIFT, and some cheaper spell-like abilities; Imps or Quasits for Alternate Form, Fast Healing, some immunities, and some spell-likes;
Lantern Archons for auras, tongues, light rays, Fly 60 feet (perfect), and TELEPORT AT WILL;
Tojanda for great natural armor, great swim speeds, and really powerful bite attacks,
Succubi for Alternate Form, Energy Drain, Spell likes, SR, DR, Immunities, and CHARISMA 26
Nightmares for 90 foot fly speed (Perfect), Etherealness and Astral Projection (yes, the 9th level spell) at will, and FUCK YOU MY HOOVES ARE ON FIRE.