I can find any track easily by it's first letter, but sometimes I can remember only the other part (e.g. Shooter in the Super Sharp Shooter). Zune Software has a search box (in full text mode), but I can't find one on my phone.
Am I missing something?
No, this is something I know many have wished for but it can't be done.
Post/support the feature request at the User Voice site
It's impossible for now. Hope to see this in a future OS update
There are apps that provide search. For example, Instant Music Search Pro provides some of the missing search functionality that you are looking for.
