Note, I found the 328P waking up by itself when waving hands over the PCB, etc
The UART may need to be disabled / powered-off. I can't remember if the startup code always initializes the UART or only initializes it when Serial.begin is called. That may explain the unexpected waking.
Runs off 3 x AA batteries
You can lower the full-power consumption considerably by running at a lower voltage. You will also have to run at a lower clock frequency. (8MHz internal oscaillator / 3V seems to be a nice sweet spot)
3.9uA current consumption
Seems a bit high to me (but still very good). I was able to get the sleep consumption below 2uA (the limit of my meter). The datasheet claims 1uA and I believe that to be accurate.
I suspect the internal pull-ups will no longer be powered in deep sleep mode
I do believe you are mistaken.