Circuit to limit a set of outputs so that only one is on
If your relays have both NO and NC contacts, you could chain the power to the solenoids through the NC contacts of the previous relay. Any time a relay activates, any relays further downstream do not receive power and cannot feed their solenoid valves.

In reality though, this sounds like it should be easily fixable in software by ensuring that the outputs can only be changed by one function.