Running on 12 V is pushing the limits of the device quite a bit more than it would to run it at a lower voltage. 125 mA at 12 V gives P = I * V = 1.5 W of power, and since there aren’t any direct routes around the device from +12 to ground, that is all being dissipated inside the device. That’s well over the maximum power dissipation of the device — typically 0.8 W.
You might consider using a separate voltage regulator, perhaps a 7805, to drop the input voltage down to 5V (and allowing it to dissipate most of that heat), and just have the high end of the solenoid connected to 12 V.
