I just found out that your iPod and iTunes will only mark a track as "skipped" if you press the "next" button between 2 and 30 seconds into it. Before or after this time frame and the skip is ignored.
That solved a mystery for me! I was skipping tracks too soon, and they weren't being removed from my random playlist. I now exercise a little restraint before bashing that skip button when it plays Steps Erasure ABBA... oh, hell, they're all too embarrassing to list.
NotBob
Pro
And just what's embarrassing about having ABBA on your iPod?

I just said that out loud, didn't I?