I organise my TV programmes by Unplayed filtered at the top then go to shuffle and it constantly plays things that have been played before, I thought the point in that feature was so you didn’t have to create a playlist every time . Shuffle is the worst shuffle I’ve ever encountered on any device in my whole life on this planet. It plays all the same stuff over and over you really need to sort that out.
Did you set the filter at the show level? This only indicates which shows have unwatched episodes, but the entire show is active. So if you shuffle from this page, it shuffles all active items, in other words, all episodes from these shows.
If you only want unwatched episodes, you need to change the view to episodes. Then you only get unwatched episodes.