Wow. I got a lot of replies while I was out for dinner, so I'll address each person individually.
Firstly, to Greynomad. As soon as I clicked on the link and saw the picture, I realised that I had seen these before in the latest Jaycar catalogue during my previous searches! Unfortunately, I dismissed these a long time ago because of two reasons. One, the inlet/outlet valves were too small and the don't come in larger sizes, and two, what the Jameco website doesn't say is that the valves are for air only, not water (See here: http://tiny.cc/kiels) :( So those are out of the question, but thanks anyway!
Next, to Jackrae. While your contribution is appreciated (As are everyone's), I don't see your idea working in my setup, simply because I don't think that having 240VAC (Australian mains power) so close to water is a good idea. Also, while getting them from the junkyard would be a cheap option at first, I would then have to get power supplies, chunky relays and etc. This is an unnecessary cost when I can just power the solenoids with the same power that I use for the Arduino. So these, once again, are an unlikely option. Thanks, though!
Last, to BenF. Your first comment,
I trust you could look at them as one inlet with two outlets and so not an issue
does make sense at first look, but is most likely incorrect. Companies like GE rarely make it easy for us hackers (I don't know why :)), and would have probably put a one-way valve somewhere inside the solenoid to make sure that there is no back-flow. However, the links you gave me made me want to cry with joy (Not really, but I was very happy ;)) because they provided just what I need. I'll probably go with the ones from Seeed Studio, simply because I need good solder connections, not screw terminals, and also because I don't think that it would be easy to find a screw-on valve connector like that. But I think that you may have solved my problem!
Thanks to all of you for helping me with this!