Here is a copy of a battery pack explanation I did a while back.
A 4 cell pack would have a 14.8V nominal rating. 14.8V would cause a reduction in power by about 22%. That should still trip the sear, but it would cut into any buffer needed to maintain operational consistency in all instances. That means you better keep the mechanism clean. It would probably be better to add an extra cell.
Don't go exactly by the rating on the cells or packs. In reality, Lipo cells have a fully charged voltage value of 4.25V so most charger limit it to 4.2V. The minimum safe voltage is 3V so most use a cutoff of 3.3V. That gives a four cell pack a voltage range of 13.2V to 16.8V. The discharge line from 16.8V to 13.2V is fairly linear and results in the 14.8V nominal rating. The calculations show a 15V average but in reality its not perfectly linear so the real average is 14.8V.
NiMh cells have a fully charged voltage value of about 1.4V but it drops to 1.3V very quickly so the 1.3V value is used for the upper value when determining average operating outputs. The minimum voltage is 1.0V, but the drop from 1.1V to 1.0V occurs very quickly so the 1.1V value is used for the lower voltage. The resulting average is 1.2V which is the industry value used for packaging. A 14 cell pack rated at 16.8v actually ranges from 18.2V to 15.4V.
Checking the voltage values of the lowest value for each pack type, it shows a reduction in power by 27% for the LiPo compared to the NiMh pack. This is worst than the 22% calculated using nominal values. As the pack gets discharged, you might end up with firing issues using a 14.8V LiPo pack.
Therefore, I would recommend the 5 cell LiPo. The overall voltage will be a bit higher using the 5 cell LiPo pack. This will cause higher current draw which will heat the solenoid more. Its a 20% increase in power consumption when the battery is fully charged. I don't think the dwell of the solenoid will allow it to catastrophically overheat. If it proves to be a problem, put a 5Watt 0.5ohm resistor in series with the battery pack. That will bring the pack down to the same operating parameters as a NiMh pack.
LiPo packs and lithium chargers in general are easily configured to be safely charged these days. An off the shelf RC charger has the ability to properly balance a lithium based battery pack and the packs have charge/discharge regulators built in so that you can't charge or discharge them past their danger point.
Except for the Automag in front, its usually the man behind the equipment that counts.