MediaMonkey [1] is awesome to find something. It's mainly a music organizer that just happens to be able to play music but it works great even with scattered single mp3 files. Autoplaylists [2], scriptable and extensive search options. Been using it for over 6 years now and never looked back :)
I definitely recommend MediaMonkey Gold. It will keep your library organized, but however you want it, with no hassle at all. And if you're insane like me and keep a flac library, you can keep an mp3 mirror for your mp3 player/phone.
And you can switch between space used and time/processing power needed. Instead of keeping mirrors you could tell it to convert the files (depending on what you connected) on the fly into whatever format you want.
[1] http://www.mediamonkey.com
[2] Autoplaylists are only available for the Gold version.