I recall a 7.5.3 CD floating around and I think it was not bootable, but only carried the disk images needed for installation.

The first retail CD to boot Power Macs which I am aware of was 7.6.

For your HDD, one never knows what the seller did with it before, Apple branded or not.

I would try a third party HDD low level utility, there are some around. Siverlining and Lido were always working for me.