Sadly, it's possible they never synced. What possibly happened is that the contacts were entered as Samsung or device contacts, not Google contacts. As a result, they won't have synced to your Gmail account. My Galaxy Note 10.1 (2014) pops up dialog and asks where I want to save a new contact when I start the process, some devices (my old Thunderbolt and 2013 Moto X for example) had/have a dropdown at the top of the new contact screen where you chose where to save the contact.
Best way to avoid that? Enter all contacts from the Gmail web interface rather than the device. Second best option is to make sure you enter the contact as a Google contact rather than something else.