4PDT relays might seem exotic now, but they are quite common when you're working on old radios, etc. As for carrying through complementary signals, that's a good hack.
There is a type of logic using Micromachined Silicon cantilever switches, operated by static voltages, capable of operation for sustained periods. They don't seem to have achieved fully non-volatile operation, but you can spend a lot of money to have a relay of this type, if you want.[1]
At one point I was hopeful this would replace relay logic, and be even lower power than CMOS.