I used WinAmp the same way you did, one big list of everything I had. I use iTunes the same way. I only create playlists to transfer music to my phone because it can't hold the whole library.
You could also just conjure up any song with the "J" keyboard shortcut that would search the entire path as well as the ID3 tags. It was so good that one weekend night in high-school, my friend and I decided to put an old desktop in the back of my Jeep on foam and power it with an inverter. We ran aux wires to the stereo and I literally just had a full-on keyboard that I could pull up while driving and get any song in my library with a few slaps of one hand without looking down even once (I knew one-handed typing skills would be useful someday). (I even tried voice command with Dragon Naturally Speaking but it only worked when the engine was off.) To this day, I haven't had such an agile interface to my music. I just use a phone now but it has a fraction of my old library and searching for things while driving is dangerous, illegal, slow, and miserable.
At least now your car can have bluetooth and Siri integration...which lets you play music from Spotify...when you have reception...or tracks from your $500 16gb iPhone which can store a few albums...ugh.
You could probably re-make that project pretty handy these days, with Raspberry Pi's and hard-drives being cheap and so on
Yeah you can randomize play in iTunes or Zune, but you have to make arbitrary playlists explicitly. You can drag tracks around in VLC but the UI isn't helpful.
I would say I knew 90% of the songs in my music collection then and probably know 10% now despite it being about the same size, purely because of a few 'helpful' UI constraints.
People sort of suggest that music changed when MP3s and Napster bloomed, but the 'end of an era' in my mind, the time when my experience of music definitely changed, is when I was obligated to stop using Winamp and start using iTunes etc in the mid 2000s.