Could be that your recover partition is damaged (as you alluded to). Or worse, your hard drive is defective.
How long has it been used?
In the end, you may need to contact Sony support. There's not much else they can/will do other than sell you recovery media.