The 1N4004 should be OK, 0v = GND.
It is usually sufficient to program the software interlock.
If you do have another N.C. contact on each relay you can wire this in series with the coil of the opposite relay, (hardware interlock), in this instance if may not be necessary?.
Max.

 

And i've just found the power supply http://french.alibaba.com/product-gs/24v-20a-waterproof-switch-power-supply-485227604.html

 

Small linear supplies are easy to make and are generally more rugged than switched type, and very easy to fix IF any thing does fail.
You do not need regulated for a 24vdc motor of that type.
Max.