I recently updated some account settings on my iPhone (gmail, apple email). Now, I am missing several contacts (seemingly more recent ones). When composing a new text message, I can type one of these missing contacts names and see their name and phone number. They do not appear in my Contacts app or in my iCloud Contacts (checked at https://www.icloud.com/#contacts). These contacts are also not in my Google contacts.
How do I restore these missing contacts?