content of our NAS wipe out, Veeam database still show entries

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 [CTRL] 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.