Tried 4x 2700mAh cells with only a Schottky diode to prevent reverse current. Managed to discharge down to the battery warning message and charge back up to the battery full message 5 times with some charge left! That is a phenomenal result equating to over 70% efficiency. The phone was in USB charging mode and the batteries did get a little warm but nothing like as much as when the MintyBoost is in use.
Bad news for the MintyBoost then, it looks like the best option is to use 4xAA cells directly without any kind of regulator. As long as the device will charge from <5V and you use 1.2V cells of course. The MintyBoost does however make it possible to use only two cells.
The enclosure I used came with a PCB that already had the USB connector and diode on it, as well as a handy power switch. It cost about £1.80 from eBay.