When it comes to the backup service... do not manually erase/delete any files!
Just to make sure were are on the same page... from the sounds of it you deleted the old PC from the console, then at a later time looked at the d:\folders\{00008086-058D-4C89-AB57-A7F909A47AB4} folder on your server and/or did a bare metal restore and saw files/name that would indicate memory of the old PC?
When you delete a PC from the console, it does not immediately delete the associated files or clusters used by the PC from the backup database.
Only during a backup cleanup (which you can trigger manually in the console Settings -> Backup -> Cleanup Now) does the system go through and throw out backup sets which have expired and determining of clusters are no longer needed (due to backup sets going away).
Even with those clusters and backup sets deleted, there still will exist a few files in the d:\folders\{00008086-058D-4C89-AB57-A7F909A47AB4}\ that reference some information about the dearly departed PC... thankfully these files are relatively small and do not impact system performance or space usage all that much. In a future update to Windows Home Server there will be a step added to the cleanup that will purge these unneeded files.
With enough knowhow it would be possible to manually remove these files... however you are more likely to break your backup database by doing so... so for now it's best to let the system do what it does.
