Honestly, I'd let him or her best mundane shackles/cells- unless the jailors were savvy enough to recognize the trouble an eladrin would pose.
Besides, just because the eladrin can escape doesn't mean they all can. If he's using an encounter power, I would allow him one use of it for this whole situation. He could escape his chains/cell, but then new pressures would arise, like obtaining the key to the rest of the cells, or intimidating the guard into helping, or, my personal favorite, taking the warden hostage until the party's release.
I've often struggled with teleporting abilities (and now in late Paragon flight), but I've kind of learned to embrace them as PC strengths and move on. Plenty of other ways to challenge those with special abilities, both in the prison scenario and beyond.