Actually there was a slight mistake in my post about get the playlist to shuffle and being able to save the play order. This is the corrected info:
Here is my random playlist work around:
1) Create a regular playlist of songs you want to randomize, you can use an existing one.
2) Create a new "Smart Playlist"
3) Edit the new Smart Playlist and tell it to match the following rules:
-Playlist- -is- -point this to your playlist you used in step 1-
Check the box to limit the number of songs, if you want them all use a high number. ie 9999
Change "selected by" to Random
Leave "Live Updating" checked.
4) Depending on the source playlist's size it may take a minute to fill in your new randomized Smart Playlist.
5) Whenever you want to randomize the list again, just edit that Smart Playlist's settings and save, then edit the settings back.
Do not delete your original playlists, just use them to add new songs you want in your randomized smart playlist. Live Updating on step 3 will automatically add them into the Smart Playlist.
If you delete the original playlist, the smart playlist will become empty as it is using the original playlist to pull songs from.
I've got a playlist with over 1,000 songs on it and this is much easier than trying to manually shuffle a playlist since randomize doesn't do anything to shuffle a playlist's order.