Oh oh! You are entering the twilight zone of Vz auto backup.
On an Android, you should (for simplicity) depend on Google/Gmail/contacts/calendar. FYI - Verizon's My Verizon website is (in actuality) a competitor to the Gmail experience. On the Vz site, there's a Vz contact list, all your emails (if you get them via Vz), etc.
What you need to do is go to your My Verizon and DELETE all contacts there. Don't freak, your contacts will still be in Google/gmail -- IF they were already there. Google/Gmail keeps your contacts (etc) in its "cloud" in cyberspace. They won't disappear, if you have them in the Gmail contact list.
Vz doesn't sync well with Gmail contacts and will often provide duplicate, outdated, deleted and incorrect data. You will also find a bunch of "links" on your X's contact list that are either old, incorrect, or deleted ... all stemming from the connection to Vz contact auto-backup.
You will need to go into Vz's contact backup periodically to clear info it has collected, even if you have not installed the auto backup. A PITA, but it WILL clean up your contacts list.
If you ever do a Factory Data Reset where you have the option to "OK" installation of Vz auto-backup, DON'T do it. Just hit skip. Although this will limit what Vz collects, you will still have to check from time to time and delete (again) whatever is there.