Half of my android contacts disappeared from my phone but are still in Gmail. Won't sync back
Check the groups the contacts appear in, in web Google Contacts. With some devices/settings only the contacts in "My Contacts" group are synchronised. (In some cases it's possible they are synchronised but not displayed or returned in normal searches.)

If this is the problem, moving the contacts back into "My Contacts" would fix it. 

You should be able to do this clicking Other contacts in the left panel, then the checkbox in the header row to select all, then click the Add to my contacts button. (If that button doesn't appear, click the groups button and check My Contacts.)