P-Channel MOSFET reverse polarity protection on NMOS array chip
To be completely safe you could pick a MOSFET that can handle the load (solenoid) currents, then the free wheeling diodes will be connected across the loads. 

Aside from the effect of the inductance under pathological conditions, reversing the power will energize the solenoid through the body diode of the NMOS transistors. Maybe I missed it, but I don't see a specification for the maximum reverse current through an output (the 0.3V negative voltage will be exceeded). Since the voltage drop of the body diode is considerably higher than the NMOS MOSFET when on, most likely, the current handling capability may be considerably less in the reverse direction.