I personally have my music in Artist\Album format anyway...so searching like that is very easy. If i want a specific album, i browse directly to it and load it. if i want a specific artist and all their albums, i can browse directly to it and load them all.
Otherwise, I have a playlist which is "all", which loads everything up, then i just chuck it on random.
That does me just fine for now...the amount of time i spend searching for stuff is minimal!
Just my £0.02