While formatted exfat, run a scan disk on the drive and be sure to check "Scan for and attempt recovery of bad sectors". If the log shows irrecoverable bad sectors, you need to buy a new drive because the PS3 is ridiculously picky. You might be able to still use it in a PC since a PC is smart enough to be able to mark the bad sectors and avoid them. To my knowledge, the PS3 is not that well designed.
If it was able to recover the bad sectors, or there aren't any, there are a variety of tricks to trick the PS3 into forcing a format (such as connecting it to another PS3 or unplugging/replugging the drive at the restore prompt) but you don't seem to have a problem getting to the format prompt.
Your data is gone completely since you formatted the drive several times and copied new data to it.