How to make iPhone delete GMail contats that are not in GMail "My contacts" any longer?
You might have to force iOS to refresh your contacts.  Goto your iPhone's Settings and select Mail, Contacts, Calendars. Select Gmail and uncheck Contacts.  Now, goto your Contacts app and it should be empty.  Go back to the previous settings screen and recheck Contacts.  After that, open up your Contacts app to verify the updates.