Yes starting with a new full backup is the best action to start over.  If there are older backups showing you don't want to see you can remove them from the console so only the full new backup shows.

You can use this method and Veeam will remove them from disk - https://helpcenter.veeam.com/docs/backup/vsphere/delete_backup_from_disk.html?ver=120

If not use the remove from configuration which removes them from the DB.

You can follow the steps to remove old backups from the configuration database.

1. Open the Home view.
2. In the inventory pane, select Backups.
3. In the working area, select the necessary backup. 
4. Press and hold the tCTRL] key, right-click the backup and select Remove from configuration.

https://helpcenter.veeam.com/docs/backup/plugins/delete_manual_rman.html?ver=120

Are those restore points marked as missing or unavailable under Home > Disk > Backups? If so, you can tell Veeam to forget those:

https://helpcenter.veeam.com/docs/backup/vsphere/remove_missing_point.html

If not, try to rescan your backup repository while your job is disabled and then check again.

@Chris.Childerhose @CarySun I wouldn't go this way as this would also delete/remove the already newly created backups and not only those restore points that are missing.

@regnor as @CABelanger he did a new full backup already, if you select the the existing backup files (restore points) not the backup job, it should be fine. I did lots of times.

Exactly my point as well. I have done this as well many times.

I’d suggest doing a rescan of the repo to ensure all missing restore points are identified and then remove the missing ones per @regnor’s guidance. As you can only target at a job or VM level within the main UI, I wouldn’t use the delete from disk option for this because you’ve got a new backup chain you’ll want to preserve.

Likewise the remove from configuration setting whilst it won’t delete the backup data from the backup repository, will remove all backup job chain information from the database, including your new chain. This is fixable by rescanning your backup repository and then mapping the backup job to the existing backup chain. So the way that the least can go wrong is with Regnor’s advice