Is it possible to develop code using the Arduino IDE, with its libraries etc, and upload those
.hex files via a regular ICSP programmer, or will they not run without having the bootloader
to bootstrap off of?
Sure, the current IDE supports in the files/menu option of upload sketch using programmer that will use your selected programmer (such as arduinoISP) to burn the sketch directly into flash without needing a bootloader, in fact if the chip had a bootloader installed prior to uploading using programmer, it will end up with no bootloader, just the sketch when completed.
HOWEVER the big question is will this change the large sketch not large enough problem? That depends on if the root cause is the bootloader/AVRDUDE or if the compiler version is the root cause. I'll see if I can play around and see if I get different results using upload using programmer on my mega1280 board.
Lefty