Hi Wolfgang,
Typically the iPhone will have one little search box at the top of the screen and there isn't room to let them choose what fields it might search on. (we're designing for 320px wide as a minimum - iPhone3).
So we use one search box for all things, so depending upon what they type into that box will depend on what we search for (thats basically the cool and also obvious bit). We almost always do "contains" not "begins with" so it seems smarter to the customer.
So if it "looks" like a phone number we'll search all phone, fax, mobile fields (in Australia its also easy to spot a mobile so we can search specifically for it).
It might look like a email so we'll search that field.
If we are unsure we'll search all important fields (name, address, phones, email, etc, depending upon the database i'm in).
This is where the browse needs to be smart, we'll only show the first (say) 20 results then in typical iPhone style you can ask for more results and it will go get them. We also have a rule that no search can take more than 15 seconds, so if it does, well stop, tell them that it took too long, give them the results we found in that time, and let them ask us to continue (again and again, if necessary - you cant have your program go off for 2 minutes doing a search!).
Its worth mentioning this is only our approach but it mimics much of the nice innovative user interface design of apple.
Regards
Bill