IIRC, Macs with New World ROMs shouldn't require a PRAM battery to boot. I know for a fact that an iMac G3 will boot without a battery even in the machine. Absent PRAM instructions, the firmware goes serching for a system folder. HD first. Then optical. At some point it should also scan the USB ports (I think). Ergo, the New World ROMs are considerably "smarter." You can override this order, and go staight to optical by holding C.

Do you have the original optical drive for that Mac, or is it a third party replacement? I have heard that some third-party drives are troublesome as boot devices. Does it look and/or sound like the firmware is even searching the CD?