I'd look at resizing the valve. Determine what your minimim sizing case is (low flow and therefore high head off the pump and low boiler pressure), normal operation (duh) and maximum sizing (maximum flow and therefore minimum pump head with maximum boiler operating pressure). Include your line losses of course.
Davefitz brings up another case (I don't work with boilers so I am not familar with the requirements), the boilers firing with the safeties relieving. Dave, is this at normal firing rates, maximum, etc? If so, this is likely the maximum sizing requirement. From the description of how your system is operating today, if you increased the boiler steam pressure to relieving pressure, I doubt you'd maintain design water rates today.
Once you have those cases, you know the Cv for each case. Compare that to the installed valve and the answer will pretty much fall out if resizing the trim or the valve is the answer.
One last question, when you say the valve runs about 75% open, is this with both pumps online? If you shut one pump down, does the valve go full open? It should via the control system if one pump as you say is unable to supply enough water.