Did they actually delete the physical company as in the directory it used to be in is gone ? Or did they simply remove it from the Sage companies list when you start Sage ?
If it's the former then you can try using this http://www.snapfiles.com/get/restoration.html to see if you can undelete it. If the sage data was held on a server then you need to run the program on there as it only works for local drives.
It it's the latter then you just need to re add the company either when you load sage press "add company" or by editing the sage company file (found in c:\documents and settings\all users\application data\sage\accounts\) Open the file called company in notepad and simply add the location of the directory back in.