Yea lots of fun!
I'm plugging the batteries DIRECTLY into the 5 volt line that powers the Arduino. That is, I'm skipping the regulator. This works because the batteries are essentially "regulated-enough" power supplies, and in fact pull the voltage generated by the solar cells down (the Arduino is off when the cells are "on" anyway).
I think that you are right. If I wanted to plug into the Arduino's "Vin" (i.e. go through the regulator) I would have to have another battery to bring the voltage up higher. For some apps, that might be a small price to pay for over-voltage protection, but for my app it should be ok to plug direct & it is more efficient.
But when I was experimenting with running the Arduino directly off the solar cells (instead of charging the batteries and running it at night), I did plug the cells into the Vin (because the cells generate 7.5 volts) and it worked in both sunlight and shade.
Yes 40ma is basically what I got too.
You project sounds pretty interesting. Since you were driving a few 1 watt LEDs all night it sounds like you are pulling and storing a lot more power than I am planning on.