Can you be sure that the PLC code isn't doing the double firing? Maybe throw a quick diagnostic rung in there with a counter on the output, see if it counts up in ones or twos.
If you can eliminate that, I would be checking on the rating of the solenoid and the rating of the output. The solenoid will have a large inrush current, and your PLC output may be current limited - perhaps the output is throwing everything it has at the solenoid to try and bring it in, then limiting and turning off for a split second, then coming back on and this time making it the rest of the way to saturating the coil so that the current drops back to a manageable level. I never ever drive a solenoid directly from an output, I always use an interface relay for this reason...
What PLC and output card are you using?