I'm all for energy savings so forgive me for a bit of a rant, then I'll get back to the electronics. To really focus the mind on where to save energy, consider running a house on solar/wind. It is a great hypothetical to work through (especially with input from people who are actually doing it). Suddenly wall warts drawing power all the time have to go. Automatic systems that turn off devices at power points are worth building. It is even worth looking at some of the dumb things we all do, like taking a house where the outside temperature is 4C, using energy to heat it up inside to 23C then putting a fridge in the middle of that heated house and using energy to cool the inside of that fridge down to 4C!
But the bigger stuff is harder to do and the small stuff like wall warts is easier, and may indeed be a bigger market for anyone trying to make a $.
Ok, we have a battery powered latching relay. If there is one coil there is no other solution than an H bridge. The coil only draws power when the relay changes so the current draw is negligable. I'm presuming you want to use the relay you have, and this does narrow down the options. I think the problem now becomes - how to build an H bridge that can run on batteries. Picaxes can run on microamps but a L293 running all the time will flatten a battery fairly quickly.
There is an H bridge circuit using 4 transistors, then another two switching transistors between the bases with 10R resistors on the collectors and 2k7's onto their bases. Bad description I know but people who have seen this circuit know what it is. What I don't know is whether it draws any leakage current out of the driver transistors' bases. If not, this could be an option.
A picaxe can power up other circuits to do the switching. Say it was running off 8V of batteries with a low quiescent 5V reg. Drive a 547, then a 557 to make a switchable 8V or 5V supply. This can drive the L293 or a transistor H bridge, kick the relay over with 1/2 a second of current, then the whole drive circuit turns off.
There are hybrid relay solutions. Use a picaxe to switch a very tiny reed relay (with or without a transistor, depends on the coil resistance), then use that to drive a L293 H bridge so you can have the picaxe sleeping most of the time, turn on the power to the L293, flip the latching relay then turn it all off. This could be fairly simple - one tiny reed relay, one L293 and two back emf diodes.
There are also relay to relay solutions. Use a picaxe to drive a reed relay (it might even be able to drive it without a transistor). If it is a DPDT relay this can become the H bridge that switches the polarity of the coil of the main relay. Use a SPDT relay to then apply current to the coil. Three relays and defiintely no quiescent current when off.
There are also non latching relay solutions. Say you are happy to have a small transformer running off the mains in the solution, but you want it off most of the time. Use the transformer to charge the batteries. When they are charged, use the picaxe to turn off the mains supply to the transformer (small latching relays like the one I mentioned earlier would be perfect for this). Measure the batteries with the picaxe and when they are getting flat, recharge them. The recharges might be only once a month for a few hours. Now there is enough grunt to run the coil of a big relay (non latching) if needed.
Personally, I think if one is using batteries the cost of these needs to be included in any cost equations that look at quiescent current draws. I pondered this some years ago and concluded that the best solution was to accept that one transformer uses less power than lots of transformers, so I have one 24VAC transformer on all the time, and that has hundreds of metres of cable running all over the place that power lots of devices. Some of these are wired and some are wireless and I'm moving more over to wireless. Mains controlling devices don't have a generic controller, but rather have relays sized for each application. So a 90W pump will have a much smaller relay than a 2400W heater.
I can think of even more brainstorming ideas. It would help to know even more about the application - eg how does it fail if the power goes off and it latches in a random on or off state and then the power comes back on? How does it fail if the batteries go flat? How mission critical is it?
Just as an aside, I have been building a lot of battery powered picaxe circuits where the picaxe needs to measure volts accurately, so it needs a regulated supply. Standard 78L05 regs draw too much power, but there is a nifty alternative the LP2950 which only draws 0.075mA. Available for only 50c from stores on ebay - international
www.ebay.com then search for LP2950. I've been getting them from a store called west florida components and shipping to Australia is taking well under a week.