Earlier quoted context omitted.
I have had the (conspiracy) theory for a while that this is by design. Kept happening to me on an account where I've disabled watch-history. Now I'm watching on an account where it's enabled and it hasn't happened even once. And it's been months since I switched. Actually not sure if it's even that far fetched. Making the logged-out-experience worse on purpose is something all the big internet firms do.
But... You've asked YT not to remember the previous videos, and it doesn't: LGTM. There could be advanced implementations (like with the remembered passwords, where YT would store a list of seeded hashes of your viewed videos). But they are that: advanced implementations, that impose an extra cost.
Though I still think "not remembering watch history" (and adjusting what you are shown based on that) to mean that a functionality that doesn't have anything to do with tracking (because it only requires information from your current session) to be a little lazy.
You wouldn't expect a slide-show of images to be shown in random order, just because you didn't consent to the cookie banner.
But in all fairness - I really like youtube's auto-play and suggestion algorithm when it comes to music. I use it for free and I haven't seen an ad in years so I don't want to complain :)