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.
