Je suis choqué : Il n'y a pas de mode "shuffle" dans VLC, juste un mode "random" tout moche.  :-(
(cf. http://sebsauvage.net/links/?40imOA)

EDIT: On me fait dire que - si si - c'est bien un shuffle. Il faudra que je re-teste (peut-être que le comportement est différent avec une playlist en ligne).