iPhone contact search (with letters) doesn't return anything
It seems that you have multiple contact accounts on your iPhone. Open the Contacts app on your iPhone, tap on Groups and then tap "Show All Contacts". 

You can now view all of your iPhone contacts in one place.