You don't necessarily need 5V to run Arduino - I have a remote control 5V 16 MHz Pro-mini that is running on 3 AA batteries. They are currently down to 4.25V total and it is still running. The batteries connect to VCC AFTER the regulator so its not wasting energy knocking 9V down to 5V.
I am waiting for a 3.3V 8 MHz Pro-mini to arrive, I plan to try that with a 3.7V Li Ion battery. May cutdown on my transmit range - but I only need 50-60 feet, so am not too worried.
If you read section 28 of the AtMega328 datasheet, they show it running at lower frequencies on as little as 2V.
The arduino can be programmed to go into powerdown sleep mode in between captures, that would extend battery life as well.
If you had 1500mAH of useful battery life, with the Arduino drawing 9mA in idle mode, that's 7 days right there. Drawing <1mA in sleep mode extends it way out. There's lots of posts on self-waking from internal timers, I haven't tried those yet, was only able just recently to wake from external interupts (missing <interrupt.h> in my sketch).
12 captures/minute x 60 min/hr x 24 hr/day = 17,280 captures/day.
SD cards hold gigabytes these days, so space shouldn't be an issue.
My Canon powershot camera runs on 2 AA batteries and shoots hundreds of multimegapixel shots on 1 pair with zoom lens and display, so this certainly seems like a feasible experiment.
Not sure how happy the post office would be about active elecrtonics being shipped around. You would have to make sure things are packaged pretty securely so the batteries could not short out & create a fire hazard.