Penso che una soluzione migliore, ma altrettanto semplice da realizzare sia la seguente:

Prima di tutto, come già si diceva, vanno copiati gli elementi dalla TListBox (L) in una TStringList (S).

A questo punto si esegue un ciclo I da 0 a (L.Count - 1) all'interno del quale verrà fatto:

- generazione numero casuale (X) compreso tra 0 e (S.Count - 1);
- copia dell'elemento X della TStringList all'elemento I della TListBox;
- rimozione (delete) dell'elemento X dalla TStringList.

Spero di non essermi scordato nulla.