For those of us relying on listen-mode to wake up the atmega328p, it occurs to me that if I were using the Moteino's regulator (as in the example under discussion), I'd be better off running at 16mhz instead of 8mhz.
You know it strikes me that if you have a Moteino with regulator removed, and thus the external 16mhz clock it might be best to keep using it but program the CKDIV8 fuse to start up at 2mhz. You can then measure VCC on startup to select the lowest clock prescaler compatible with your current battery conditions and thus optimize performance.
Drawback is some of the Arduino library functions (e.g. delay()) won't work correctly since they're hard coded for a given CPU speed.
The ability to change frequency "on-the-fly" also seems like it may be necessary if you want the option of utilizing every bit of available energy all the way down to 1.8v, especially in your coincell scenario where the voltage might nosedive while in use and not recover until later. I guess you could sample the voltage from time to time and if the voltage is running low at the current frequency, force a reboot and then do as you suggest above. Or maybe there's a more elegant way to transition from one frequency to another?
Somewhat related: I get the impression the bootloader is hardcoded to run at a particular clock speed (mostly 16mhz or 8mhz on this forum). Is that true? If so, maybe it should be harcoded to run at 4mhz (or perhaps even less) if you want to maintain the option to do wireless programming all the way down to rock bottom 1.8v?
Anyhow, sorry for my ignorance, or if this has already been covered in depth somewhere else, but I'm just trying to visualize the final target so I can better steer my development toward it.