I finally managed to get Apple support to take a look at the issue over a remote session. In my specific case, and I suppose for others here, the problem seems to be the lack of Apple's APFS filesystem by some external HDD models. My disk is over 4 years old and I cannot get firmware updates to fix this issue. Even if you format the disk as Extended Journal, the Time Machine still changes it to APFS causing this issue to come back for affected disks. I'm using the disk for ext storage now.