H-Bridge and bi-directional solenoid
I had a look at the link for the solenoid and the datasheet for the IC used in the H-bridge board from ST found here: https://www.sparkfun.com/datasheets/Robotics/L298_H_Bridge.pdf

HandyHowie made a good point.  The details of the solenoid specify 12V DC, 53 Watt nominal power (not peak power as it starts to move).  This gives you a current of 53W/12V=4.417A (approximately).  Remember that the switch on (rush-in) current for an inductive load (solenoid, motor...) might be many times this figure.  The fact that it works when you connect it MOMENTARELY to the power supply, which is only 2A, might be because every power supply has (or should have) a big capacitor at its output to help with these switch-on currents for inductive loads (like your solenoid) or for any circuit that needs to charge its capacitors before it starts to operate.

Therefore, your power supply might NOT be good enough for the task.  Also remember that applying Ohm's law, the load (assuming the resistance does not change) will require more current for a supply voltage of 15V instead of 12V.  I calculated a resistance of approximately 2.717ohms, so the actual current at 15V should be 5.521A.  However, your power supply might be good enough, depending on the load you want the solenoid to move, which means how many Newtons of force it must produce to move it, hence how much current it requires to operate.

In addition, if you look on the first page of the datasheet for the H-bridge IC, you will notice the RSa and RSb sensing resistors which are used by the control circuit to obtain feedback regarding how much current goes through the load.  I admit that I didn't read the full datasheet and I have not made any attempt to obtain a schematic for the H-bridge board you are using; however, the L298 has two bridges and is designed for a total current of 4A (2A per bridge) or a non-repetitive peak (100 microseconds) of 3A.  You can however connect it in a different way to have higher currents (Figure 7).  The previous mean that maybe the control circuitry senses the current overload and 'intentionally' reduces the voltage to reduce the current through the load.  On page 7 of the datasheet it says that the control circuit can start chopping the output to reduce the current, so the 7.5V you measure might be the RMS, the True-RMS, or the average (depending on the instrument) value, after this chopping action (if it happens).  An oscilloscope could help clarify this.

Alternatively, the reduced voltage might occur because the saturation voltage (figure 1 page 4 of the datasheet) goes up.  The datasheet gives a value of 2.4V saturation voltage for 2.4A of current.  It is unclear to me if this voltage is for just one or for both transistors of the H-bridge arm that complete the circuit, however, you can observe that the relationship is not linear, so for 4.417A at 12V I expect at least 4.417V of saturation voltage.  The situation is even worst for 15V as the current should be 5.521A, so the saturation voltage must be at least 5.521V.  So, the 7.5V you "loose" might be because of the non-linear relationship shown in Figure 1, or because Figure 1 refers to each transistor (and remember you have two in series with the load, which is located in between the two transistors in an H-bridge configuration).  Keep also in mind that you might burn your IC H-bridge at these high currents.

A further location where you might be 'wasting' voltage is across a component outside your H-bridge IC due to the high currents.  The board I can see following your link seems to have more external components....  it also looks as if it has a small surface mount control logic IC made by ST (perhaps the L297 shown on Figure 8 of the datasheet?  You can see it here http://www.st.com/content/ccc/resource/technical/document/datasheet/f9/35/6e/3f/48/18/48/51/CD00000063.pdf/files/CD00000063.pdf/jcr:content/translations/en.CD00000063.pdf).

In summary, as a novice, I would have chosen to go with a different H-bridge and a power supply at 12V and much higher current (if needed to move heavy loads with the solenoid).  Then again, as an electronics' engineer I would have built a circuit with discreet components and a resistor to absorb the extra 3 volts so as not to overheat my solenoid (if needed).  The cost and footprint would have been roughly the same, maybe even better....

I hope this helps,

Best of Luck,
Konstantinos