I’ve just ordered another cable, which should arrive next week. I’ll report back once I’ve tested it.
Although I would just mention that the cable I’ve been using (the official RPi cable) does have “high speed HDMI” written along it.
For what it’s worth, I downloaded the latest version of Raspbian Buster (kernel 4.19) and tried that on the RPi4. Sadly (and perhaps not surprisingly) I had the same problem.