Yeah, but No song appears in more than one playlist. on my player. Well, maybe it does, and it was not on purpose and I am not aware of it...

You are the second person to report something like this. Someone else was also saying that their song count was changing in unexpected ways, and that the shuffle de-dupe feature could not possibly be accounting for it because they didn't have copies in their playlists. I don't remember the resolution to this, it could have been a PEBKAC or it could be something else. Don't know. Let us know how it comes out.