A lantern archon (Monster Manual 16) has the archon trait teleport, a supernatural ability allowing it to "use greater teleport at will, as the spell (caster level 14th), except that the creature can transport only itself and up to 50 pounds of objects." A lantern archon has 1 Hit Die.
A bag of holding (type III) (7,400 gp; 35 lbs.) holds 1,000 lbs. (probably enough for the four Medium or Small creatures and their undead assistants depending on what kind of undead assistants they are). The bag is well within a lantern archon's teleport trait weight limit unless the lantern archon is otherwise burdened by whatever gear the DM determines a lantern archon totes around (e.g. snacks, a guitar, lamp oil). Wiggling into a bag and letting someone else do the teleporting is legit, although trust is a necessity.
The 1st-level Sor/Wiz spell reduce person [trans] (PH 269) et al. will vastly increase the bag's ability to tote the party. Just don't overstay and exhaust the bag's 10 min. of air. However, this method transportation does require PCs to accept that sometimes being an adventurer is a bit humiliating.
Outside the core rules, instead of the bag of holding and at less than ¼ the price of a portable hole (DMG 264) (20,000 gp; 0 lbs.), the 50-ft.-deep enveloping pit (Magic Item Compendium 159) (3,600 gp; 0 lbs.) can accommodate a small army (okay, a Tiny army) and should be more than sufficient for the entire party—including the party's 2 1,000-lb. undead hangers-on—for the few minutes it needs to teleport. While it's one of the game's best magic items at the price, employing the pit at all usually mandates a LE, LN, or NE alignment, but this requirement can be bypassed with a successful Use Magic Device skill check to emulate an alignment (DC 30). It can be challenging to succeed on such a check, but even a little optimization should make success possible.