sometimes you want to change the area claimed, but as far as I know there is no way to reset the map on the deed other than having someone explode the pedestal to get the nether star back (is it possible by the pedestal owner?), adding a way to craft the deed back into a nether star would solve this, or making the pedestal explodable by the owner.
I also noticed that you don't get the pedestal back after mining it with a pickaxe, is that intended?

No, there is not an other way, which is (apparently) by design.