Due to having a conservative bent about mobile bandwidth, I do all my music discovery, starring and playlist editing at the computer, then sync to mobile everything starred and a subset of playlists. Once truly mobile (i.e. away from WiFi, away from PC) I don't download any music. None. Zilch. The offline play is a HUGE feature to me.
So - why so hard to search for a song that's already on the iPhone? If all I wanted was blind random shuffle, guess what I'd buy? An iPod shuffle (and I don't want one).
No sort-by-artist. No sort-by-title. I need to the ability to search within what's already on the iPhone, NOT what's on the internet.
You've made it rather difficult to find and play what I've already decided to sync-to-mobile. Please make it easy.