I tested my circuit with a resistive load (light bulb) and it worked perfectly through dozens of tests so I guess my problem is with the load and the current it draws.
Is there any way to further isolate the relay? Maybe these relays are too susceptible to interference.
After doing more tests on my circuit I finally found my mistake.
Here it is:
When I built an initial test circuit I thought I was having issues with the load current but the circuit was poorly built. The parts were laid out almost randomly and I had parts on both sides of the board. When I built my final circuit, in an attempt to minimize the possibilities of interference, I laid the parts out more linearly, kept the relays at one end of the board and even used a shielded wire pair on the output of the relays. whoops! I had tied the shielding to ground and this was inducing enough current in the relay coil to make it's opening sometimes unreliable. After I removed that connection the circuit worked perfectly. Thanks to everyone that helped!
This was the first electronics project I've attempted in years and the outcome has been so satisfying I'm thinking of starting another project. A solar tracking system perhaps?