There are probably different reasons. I would imagine it's primarily chemical in nature, and some sort of petrification process takes place. I've a boat keel that is almost 70 years old, and the places where the nails went through are noticeably harder than the rest of the wood. That, and the fact that rust itself is abrasive, would add up to: sandpaper nails embedded in rock.
We should ask LisaB. She's a wood chemistry guru.
My knowledge of chemistry: Different kinds of atoms like each other, and form bonds. The end.