Bernard,
I see you are using 22k resistors on the ULN2804 inputs. Are you remembering that they have internal 10.5k resistors in series with the bases?
Thanks Bernard - well, 12v/10.5k ~= 1.14mA, so the internal base resistors are plenty large enough. With the extra 22k resistance, you have a total of 32.5k, and the base current is only ~ 369uA. While that should still allow the driver to work OK, they are 8 resistors that could be eliminated, saving on soldering and a bit on costs.
OK, I've formalized Bernard's schematic, which means attention to detail.
Rather than adding a 9th CMOS gate I went with the diode version. The base design can live with one such gate, multiples would introduce major diode drop problems. Again, I've never built this, but am pretty sure it will work as is.
The IRF510 is one of the poorer parts out there, but Radio Shack carries it. Most MOSFET in the TO220 case style have a conductance much less than 0.1Ω, which means they can carry significant currents without getting hot. The IRF540 is a good example of this.