Unfortunate, but not a deal breaker. It comes down to availability and reliability. Which is better for you, two relays with contacts rated for at least 4 A DC, or two power darlington transistors (TIP125)?
BTW, I wasn't suggesting changing the solenoid power supply, just the connections to...