From a game balance standpoint, a permanent Petrify is no worse than a lot of the other, very legal, things players can do. A slap-patch of Slab can be used by anyone, and costs a couple hundred nuyen, and immediately drops someone into total paralysis, making it a one shot killer, only defended by toxin resistance and an attack roll. How is that better, from a balance standpoint, than a spell (which can only be used by those who invest priorities to gain the ability to cast spells) that costs the equivalent of 10000 nuyen (5 karma), plus whatever costs for the formula (either in time and nuyen to track down someone to write a formula for you, or karma in buying the Arcana skill to do it yourself), and is resisted by spell resistance and an attack roll, and also is going to draw aggro like walking into a KE precinct with a Panther XXL? Both are instant kills, but one takes a lot more work to set up, and is a DAMN sight more likely to make you feel like a clay pigeon if you do it too often, or where there are witnesses. As a flavorful tool for covert assassinations, it is pretty badass, especially if you have a cover as an artist who uses magic to shape sculptures (which is more resources pumped into this trick). But how many times are you really going to get a chance to use it over the course of a run, without bringing worlds of hurt on yourself? Whereas that slap patch will get less attention turned your way than the sammy's AK-97.
And Kiirnodel, it depends on the spell, and what was done to change the person back. A ritual to change them back may be able to fix things, even if it was a permanent spell. Pattern magic (which was mentioned in Forbidden Arcana) could potentially do the same. And there's a lot of stories about magic being done to change someone where they didn't get changed back, especially when you start talking about witches and curses or hexes.
But I stand by the idea that such things aren't unbalanced, as far as mechanics go, but due to lore they should be things that any players who get their hands on them should be circumspect about using, since they feed into the worst stereotypes of mages, which tends to bring the pitchfork and torches crew around.