I think you can choose to only move in songs that you don't already have on your shuffle. I've always had this problem with my shuffle, so I'm not sure of a proper fix.
Human history is the story of complaisance. While disaster is fresh in our memory, we take precautions. But as the memory of disaster recedes, we start to take risks.