I'd first be inclined to make sure that it is the PSU that's at fault. Given your description of the problem, my first thought would be that you've just pushed the OC a bit too far, and the cards aren't capable of handling it. Try backing them down a bit.
Power consumption increases linearly with clock speeds. At stock settings, those 7800GTXs will pull about 80W each, most of it from the +12V line. Increasing this number linearly with your overclock should give you a very rough idea of the overclocked power consumption.
When a PSU is overstressed, it will most often cause a decrease in the voltage on each rail. If you have a multimeter, try measuring the rails under load (particularly the +12V). If not, you can measure it with software, but the results won't be so accurate.
Having said all that, a 7800GTX SLI will really push an SPII-500. If you do intend to upgrade, a budget would be nice.
