Clever way of starting-up relays discussed in this app note from Maxim Integrated. via dangerousprototypes.com
Relays are often used as electrically controlled switches. Unlike transistors, their switch contacts are electrically isolated from the control input. On the other hand, the power dissipation in a relay coil may be unattractive for battery-operated applications. You can lower this dissipation by adding an analog switch that allows the relay to operate at a lower voltage.
How to lower relay power consumption – [Link]
Have you looked into magnetic latching relays? Zero power to hold in on or off state. Only a little pulse is required to flip the state.