Thanks for posting on this and taking time to call Apple. Did you hear any news on the 26th ? I have the same problem, and use a MacPro 2019 Intel Tahoe 26.3.1. Computer bought new, so refurbishment not the issue, its something new after an OS update perhaps. Private relay is stuck like you describe, but even though it shows as "OFF", I think it is active ON. I know this because if you go to Google Scholar (to search medical journals, for example), Google will not let you search if you are using Private Relay. So when I need to do those searches, I turn PR off. Anyway. I'd rather have it stuck on, but this is a pain. Hope you hear more form you and that this is solved.