This is expected behavior. As far as Veeam is concerned, what you did was add new VMs to the jobs, remove old VMs from the job, and then told the job to mark datablocks in the backup files associated with the old VMs as unused. There probably was some deduplication between the two VMs in the backup file (depending on settings), but other than that, Veeam identifies VMs only by their ID, not by their content.
In previous versions, you would have to run a new active full backup, and then allow the old full to be deleted by your retention settings. In v9, depending on your job settings, you may want to schedule a compact operation