I made a wall-skull 1 block structure to use as arandomly placed decoration, but while it does rotate it, it randomly rotates it towards the right direction on in the opposite one.
Structures to test (WMzI is the parent):
active.zip

Are you sure it's not just skulls in general that don't work?

That also happens with Witchery moss (didn't include that as it requires another mod) and the skull gets rotated, just not in the right direction sometimes.

Some blocks don't rotate correctly - when I asked Lex about it he said it was because it wasn't 'standardized'. Try with just the skulls in a small normal structure - if that works but it doesn't in structure blocks I'll investigate :)

To be more clear, in the small normal structure they rotate correctly, the "still happens" was related to Mirrored on/off.

Still happens, I even tried with Mirrored On/Off, and by placing the small normal structure in a list and spawning the structure generator in another structure.

This also seems to happen with some stairs, and those aren't in a separate substructure, but in the same structure as the maze component itself.

Ok, the problem, it seems, stemmed from mirrorability, as turning Mirrorable to off for all maze components and child structures eemed to fix this. The stairs still don't work, but as they're from amod I didn't really expect them to.