Hi, this was exactly the kind of compatibility that I wanted in a MP3 player for the PSP, but like you, I couldn't find one that sorted songs like that.
Well, I did a homebrew trying to achieve this goal with a friend a year ago as a project for college. The bad thing is that you have to use an application in your PC to transfer the 'library' and playlists to the PSP. (The idea was to do something sort of like iTunes and iPod).
The PSP part is kinda buggy and dies with certain MP3s (I don't know exactly what is the reason), it doesn't have visualizations and the cover art is retreived from the file "Folder.jpg". The PC part is really buggy xD but works to transfer songs, library and playlists.
I never released this publicly because I think it's just too unpolished and the name is already used by another homebrew.
But who knows, maybe you might find it useful.
Here is the site where we published all the documents, source code and binaries (unfortunately both apps are in spanish):
http://sites.google.com/site/gammaraypei/documents
The first two downloads (jTunes.tar.bz2 and pspTunes.zip) are the sources+binaries for the PC and PSP applications. (Credits for the PC application goes to my friend SparkS)
I tested it and used it in my PSP 3001 (3g) with ChickHEN + 5.03 GEN-C.
I know this is my first post but this is not a virus or anything like that and wouldn't brick your PSP.
I've been wanting to improve this homebrew so it doesn't need the PC application but I been kinda busy with college. Right now I'm on vacation so maybe I could finally do something.
By the way, VisMP3 looks like a really kick-*** player, too bad it didn't work. If you find
PS. If some dev reads the code, please don't laugh. I know it's kinda messy and not very well structured xD.
THIS APPLICATION IS NOT RELATED IN ANYWAY TO 'pspTunes' BY 'Bigbondfan'.