settings search in mail in iOS 9 is strange. It sorts by contact first, then subject. It used to just filter emails. Is there a way to go back to that or modify these settings?
I'm having the same issue. Hopefully someone chimes in with a fix. I'm also not able to search my company's global address book anymore either.