I've seen similar stuff happen - often with the "marked" flag. It was annoying for a while with no UI to change the flag on a playlist (JEmplode now supports this, but didn't at the time). I had to change my stored search to select only marked tunes.