This is expected - Fusion can't tell if the virtual machine was located on some removable media (and thus might be back at a later point) or if you deleted it. Select the entry in the Virtual Machine Library and press delete to tell Fusion to forget about it.
By popular request, in Fusion 2.0 you can shortcut this. Instead of deleting the virtual machine in the Finder and telling Fusion to forget about it, you can skip the first step and go directly to the second. If Fusion can still find the file, it will ask if you want to delete the virtual machine from the disk or just have Fusion forget about it.
