Finally I managed to fix the recording issue. But it was something I certainly did not even think of doing. Here are the steps I did:
First I thought full factory reset would fix the issue. I did the reset, re-registered the HDD, but still the HDD would not be recognised when opened the Title List. Also could not start recording. Also right after the reset, I still would see the flooding of the errors in the logs, see previous post. So the situation was exactly the same like before the reset.
Then I looked again in the Title List, there is also a Recording Error List. It was full of errors, even though it was a new HDD (nothing was recorded ever to it) and the errors seemed to be from the previous HDD that I used. First thought would be, why do I see those errors after reset and switching to a new HDD??? This only Sony knows (hopefully). Well, I thought, I will delete all the errors from the error list. Then I re-registered the new HDD again and voila, no more problems. No errors and could record again. Also checked the system logging (adb) and the error flood is gone! I must say this behaviour is very strange and Sony should definitely look into this...
