Yes, that will hapen if the Malware add its nameto the exe-call in the registry. If you delete the Malwarefile, windows try to execute it before starting any Exe-file but can not find it and so windows gives you a message that it can not find the "malwarefile". Maybe there are some entries leftover in the registry, whichyou have to fix manuall.
It would be helpfull to know the name(s) of the Viruses Panda deletes, to find out which entries it has modified.