Have you considered that there may be a hardware issue? (Bad CROM, cable, controller, etc).
Do you have access to another CDROM you could swap out? If that doesn't help (since you're OK with disconnecting the HDD), try using the other IDE controller. If availability allows, also consider replacing the cable...
Just some thoughts for troubleshooting areas