listing what you have done but I didn't see trying a different hard drive (they do die and when dead fail to get recognized by the BIOS) nor different drive data cables (again, they can and do go bad resulting in power to the drive but no data transfer resulting in BIOS not seeing the drive).
Are the Hard drive and CD both on the same data cable? If so, if one has problems it can cause the other to become invisible to the BIOS. IDE isn't as bad about this as SCSI but it still happens.
Have an older Dell 8200. Boot failure with no previous problems. F2: shows a: drive, but "primary drives not installed." Boot Sequence: CD and hard drives "not installed." Error message re: Plug & play error and hardware configuration error. Floppy Boot disk doesn't work. Copied files from another computer with similar configuration, but didn't work