It seems that you can only search for a name or a company name in iOS's Contacts app. You can't search for an address, a zip, a note or any text outside of those fields. The same holds true for searching in iOS/Spotlight.
Besides the third party app for finding contacts via phone numbers mentioned before on this site, is there any way to search for an address, a city, a zip code, or a note in the Contacts list in iOS?
Not that I am aware of. Contact searching on iOS is particularly limited, it will only match whole words in names too when used via Spotlight, although you do get on the fly as you type results when searching directly in the app.
No real reason why it works this way, other than every extra piece of data that you want to search requires indexing, which requires time and space. The search function in the iPhone doesn't scan your data for matches, this would be far too slow. Instead as you create or update data (including contacts, calendar events, receive email etc) iOS indexes certain components of the data. With contacts, it clearly decides not to index all fields, and just does names and numbers, skipping addresses, email addresses etc. Just one of those decisions I suppose, there is limited storage available, and we already complain when a 16Gb iPhone only has 14Gb available out of the box etc.
