VLC 1.0.1, and previous versions, has this issue. I don't know what causes this, because WMP and other tested players, and even few other PC's do not have this problem.
When VLC is in fullscreen, sometimes Start bar of XP popsup in front of movie, so I have to press the "fullscreen" video to bring it back to front.
This is not the issue with "keep taskbar in front of other windows", because it happens again.