I actualy just finished a Perl class last week, and one person's final project was exactly this. It was actualy a really cool script from what I saw of it. It presented you with a list that looked similar to windows explorer, and created folders for any real folders in the directory, or any artist which you had more than a certain numer of mp3s for. I'm not sure how it handeled albums, as this was only a five minue presentation. You could click down into the real directories or the virtual directories and select mp3s. It also had a searching interface to look for specific songs.
If you're interested, I can see if he's interested in sharing. You'd have to have a semi-decent knowlege of perl to customize if to be exactly what you want, but it could end up being exactly what you want...
Matthew