Immune: undead, constructs, outsiders such as angels and demons

A petrified character has been turned to stone and is considered unconscious. If a petrified character cracks or breaks, but the broken pieces are joined with the body as he returns to flesh, he is unharmed. If the character's petrified body is incomplete when it returns to flesh, the body is likewise incomplete and there is some amount of permanent hit point loss and/or debilitation.

Marius, Scholai Armsmaster says: When facing creatures like medusa and basilisks, wise slayers prepare spells like Break Enchantment (clr5, sor/wiz5) or Stone to Flesh (sor/wiz6) if available.  Since many monsters petrify with their gaze, blindfolds and mirrors can also prove highly effective.