Solution: Bump down the cost one step.
Tasks of 1 min/caster level: 25 gp/HD for tasks of up to 1 min per caster level,
100gp/HD for tasks of up to 1 hour per caster level.
500gp/HD for tasks of up to 1 day per caster level.
Nonhazardous tasks have that amount, hazardous tasks typically increase it. Few creatures will take a task that seems suicidal.
Lesser: up to 6HD, 50 xp cost.
standard: 1 or 2, no more than 12HD, 100 xp.
Greater: 1, 2 or 3, no more than 18HD, 250 xp.
So summoning a pit fiend (18 HD) for 1 minute per caster level is now 450 gp and 250 xp. Seems fair to me for a CR 20 creature. Or you can get a 9-HD succubus for 1 day per level at a cost of 4500 gp and 100 xp. Again, fair. I think that a rule that allows rebalancing with such simple changes as these is far, far superior to the 3.0 planar ally spells.
Incidentally, Shard: Clerics can't teleport. Also, CR 12+ mercs aren't particularly easy to come by, and finding members of PC caster classes (the closest analogue to the diversely-powerful outsiders possible with the planar ally spells) is likely to be more difficult still.