You could use a small LiPoly instead which gives you plenty of head room.
Also at 3v you are grossly overclocking the 16mhz Moteino. You could change the fuse to run on the internal 8mhz oscillator instead but you should also desolder the regulator.
The last thing I want is a rechargeable battery. I want to deploy these units in the field (quite literally) and forget about them for 2-4 years. I also want them to stand up to harsh weather conditions, although not as severe as Michigan
hence the choice of Li FeS2. A couple of AAA batteries will give me 1250mAh capacity, operate as low as -40C, have LONG shelf life, and, as I said, will easily fit in a PVC/Copper tube with a Moteino on one end and my sensors on the other. Also, a couple of fresh batteries will have an open circuit voltage of ~3.6V and, while operating an active Moteino, drops down to about 3.2V nominal.
I do like your suggestion about dropping to 8Mhz as this should be plenty of performance for these applications although 3.2V at the processor would be better than running at 3.7V at the PWR pin with 0.63V dropout at the regulator.
Also, I agree about pulling the regulator from the board. I had overlooked the fact that it is going to try to drive the output to 3.3V and can't so the current draw will be higher than quiescent due to this (as shown in the Ground Current curve, figure 2-4, in the MCP1703 spec).
Regarding changing the frequency to 8MHz, you say I could "change the fuse". This sounds pretty drastic and permanent. Is it? And, if the base frequency is changed, do the standard delay(), millis(), etc still work properly or do these need to be scaled???
Thanks for the suggestions,
Tom