Hmm.. OK, Figure 1 (On-Region Characteristics) seems to be saying that with 5v on the gate, anything over 1v through drain and source would exceed 0.5A without any external current limiting. I don't see how that affects the ability to drive it, though..?
Hypothetically, the solenoids would be running at 12v, but have 20-30 ohms resistance. My calculations put that around 0.4 to 0.55A total current. Within safe limits, especially assuming 20 ohms is a temporary worst-case.
However, I haven't taken dissipation into consideration up til now. That presents a problem: It looks like there's a duty cycle for high-current applications. At 25c ambient, 100% duty cycle use is limited, linearly, from 12v @ 50mA to 2v @ 400mA. OK, so not so well suited to this application.

Again, I haven't learned all there is to know, so this is purely a what-if in case my assumptions and datasheet reading skills aren't quite up to snuff. Hope this is relevant to someone besides me.