In all those "why doesn't it reshuffle" scenarios you mention, I would then have to hear same tracks again. I don't want to. I want to hear everything, some today, some tomorrow, some next week, until I've heard it all.

Unless I do want to hear things again, in which case I toggle the Shuffle button.

By design, I decide. Rebooting, restarting iTunes, picking a particular song then going back to my long playlist, those don't decide for me.