i got a suggestion:
search bar in portrait mode! and maybe it can show when camera button is half pressed? it can also work in landscape, but in portrait it is necessary because sometimes it's difficult to scroll 800 songs.
Best solution is to make something like in symbian (v5; ^3) in contacts, but as i said search bar shows after pressing something