My bad, I said TPIC6C595 when I meant TPIC6A595, which is the data sheet I linked to.
So the peak current is 1.1A for a single output, not 500mA, but as GM says, that is for <100us. Your solenoid will probably hit its peak current for a moment but probably still too long.
Apologies ewen, back to your FET hunting...