You can drive lower voltage relays from higher voltage supplies via PWM. The relay coil is an inductor, so current does not change instantaneously, so you end up with a ~triangular current waveform with the ripple vintage set by the PWM frequency and inductance of the coil. Your MCU could measure the supply voltage and decide whether or not to PWM the coil (or at what duty cycle) accordingly. PWM can also be used to reduce power consumption via "peak and hold" drive, where a higher "peak" power is initially applied to actuate the mechanism before switching to a lower "hold" power to maintain its position, which could be useful to reduce the demands on your power supply, although I'm not sure it would help enough that I'd want to use a linear regulator for 24->12V in an application like this.
Of course you will need to deal with the EMC implications of PWM, but that shouldn't be too difficult.