Have you also tried clearing the system cache as well if you've already cleared the app cache & data?
Geo-restrictions could be a factor , although it would be incredibly odd indeed for run of the mill media to be blocked on a large scale.
Agreed, testing with a VPN is a good idea & it may be a viable workaround you can use for the time being.
Otherwise, try testing some media that just wouldn't be considered "sensitive" anywhere, and/or content specifically from Australia that would be utterly pointless to block out for resident Australians. It may at least help you confirm if it's just certain media that's being blocked out from your watch history or if it's everything you watch (Obviously, if everything is being blocked out, it's probably another issue.)
I realise it's a giant pain in the backside, but sometimes the way apps interface with the OS or your Google account can also become corrupted or experience issues & a factory reset can successfully clear them. (It's unfortunate, but it does happen.) Certainly worth trying if it will clear this issue once & for all to allow you to use the device as you'd prefer
.