This has now been resolved - despite being on an IPv4 only connection, Private Relay was using IPv6 where the DNS update had been overlooked. tldr: make sure to update IPv6 DNS if you have that.

Up to around 96 hours since the DNS change and Apple Private Relay still directs browsers to the old server. What is going on?!