I always suggest to format the pc and reinstall the operating system. This is because you can't know what damage was caused and if any further malicious code was executed as known. This can range from other hidden, malicious functionalities up to backdoors etc.

I have seen and studied a lot malware and can say, that a skilled coder with some creativity can cause huge damage. As many source codes are available, people often modify the existing ones to add functionality or modify it in some other way, which results not only in rapid developed malware.
Also if the attacker has only the binary of an already existing virus it is possible to add functionality, even without source code (or modify it in another way).

Although it may take some time to clean 500 machines, I am pretty sure, that there are tools which allows you to do so through network. This means you can clean them simultaneously. As soon as I find the tool I am talking about, I will make another post (can't find it right now, but I know that there are such programs available).
Keep in mind that when cleaning the machines properly it would be hard to investigate how this could happened and search for further evidence.

One big problem which came to me mind is when I read about that all exe-files were renamed. As the virus probably did not store in a textfile which files he renamed, you hardly can't fix this problem without reinstalling everything. And then still some files from the operating system may not work, which means, you have to reinstall the operating system too.

For such and other cases a company should have disaster recovery plans and regulary updates.

Please keep also in mind, if you don't have any recent updates or can't for some reason use them and have to backup some of your files on the infected systems too, that you may backup the virus with your regular data too. Advanced malware often attaches itself to other files and once they are traded or restored from another location, the virus is executed again and repeats infection.

Hello Hack_80
I have some experience in helping home computers with malware removal through various malware removal sites but I've never helped a complete network so please go through my suggestions only after proper discussions with you security team. Some of the tools used could harm your computer.

A) Firstly, did you try to find the source of the infection?
 What CDs, USBs have been used in your computers within the last   4-5 days? What new executable files have been used?

Without finding the source of the infection you're at risk of being infected again.

B) Try to have a proof of infection for future cases.
 Anything like antivirus log files etc.

C) Start with your most critical systems. Isolate them and clean them first. Then move on to the next critical systems

Now let's start with the cleaning process.

1) PREPARING LOG FILES
The first step that we perform is to ask the user to provide us with the log files of HijackThis from Trendmicro. However, since the no. of systems is large I wouldn't like you to post the log files here as analysis of each log file takes about .5-1.5 hrs. But keep the log files for your proof and future analysis.

I list the steps of using HijackThis here:-

Download HijackThis from Here .

• Choose the default location of C:\Program Files\Trend Micro\HijackThis as the destination.  HJT needs to be in its own folder so that the program itself isn't deleted by accident.  Having the backups could be VITAL to restoring your system if something went wrong in the FIX process!  
  
• Click the Install button.  
  
• Accept the license agreement .
  
• The progam will place a shortcut on your desktop.  This will make it easier for you to access the tool when required.  
• Click Do a system scan and save a log file.  A Notepad file will open.
  

DO NOT MAKE ANY CHANGES OR CLICK "FIX CHECKED" UNTIL YOU USE OTHER TOOLS OR RECOMMENDED BY A HJT LOG ANALYZER, AS MOST OF THE FILES ARE LEGIT AND VITAL TO THE FUNCTION OF YOUR COMPUTER


2) MAKE A REGISTRY BACKUP
Having a registry backup is essential to make sure that if something goes wrong during the cleaning process you can restore to the previous settings (Having an infected system is better than having no system at all ...)

Backup Your Registry with ERUNT

• Please use the following link and scroll down to ERUNT and download it.

http://aumha.org/freeware/freeware.php

• For version with the Installer:

Use the setup program to install ERUNT on your computer

• For the zipped version:

Unzip all the files into a folder of your choice.
Click Erunt.exe to backup your registry to the folder of your choice.

Note: to restore your registry, go to the folder and start ERDNT.exe


3)TEMPORARY FILES REMOVAL

Please download ATF Cleaner by Atribune.
Download - ATF Cleaner»
Double-click ATF-Cleaner.exe to run the program.
Under Main choose: Select All
Click the Empty Selected button.

(If you use FireFox or the Opera browser
To keep saved passwords, click No at the prompt.)

It's normal after running ATF cleaner that the PC will be slower to boot the first time or two.

PREPARE A HijackThis LOG FILE AFTER THIS STEP

4) Initial Scanning
We'll do some initial scan to remove some small infections.

Please download Malwarebytes' Anti-Malware to your desktop.

• Double-click mbam-setup.exe and follow the prompts to install the program.
  
• At the end, be sure a checkmark is placed next to Update Malwarebytes' Anti-Malware and Launch Malwarebytes' Anti-Malware, then click Finish.
  
• If an update is found, it will download and install the latest version.
• Once the program has loaded, select Perform quick scan, then click Scan.
  
• When the scan is complete, click OK, then Show Results to view the results.
  
• Be sure that everything is checked, and click Remove Selected.
  
• When completed, a log will open in Notepad. Please save it to a convenient location

PREPARE A HijackThis LOG FILE AFTER THIS STEP

5) THOROUGH SCANNING
We'll now do some scanning with SDFix.

Note:-Using this tool may adversely affect your system. Please read all the instructions before running this tool.

A complete tutorial on how to use this tool is available in the below links:-
http://www.bleepingcomputer.com/forums/topic131299.html
http://forums.majorgeeks.com/showthread.php?p=869653

PREPARE A HijackThis LOG FILE AFTER THIS STEP


6) IF THE SYSTEM IS STILL INFECTED
If your system is still infected then use this tool to scan your system.


Caution:Read every instruction before using combofix.Using this tool in wrong way may adversely affect your computer.

Here is the complete tutorial with download link on how to use combofix.
http://www.bleepingcomputer.com/combofix/how-to-use-combofix

Download ComboFix by sUBs from the above link

Note: If you already have a copy of ComboFix on your system it is essential that you delete it before downloading this copy.

**Save it to your desktop**

We need to disable one or more of your security programs so that they do not interfere with ComboFix.


Double click on ComboFix.exe & follow the prompts. If you are prompted to install the Recovery Console I recommend you go ahead and hit yes.
When finished, it shall produce a log for you. Please save that log to post in your next reply along with a fresh HJT log

Note:Read them before continuing

   1. Do not mouseclick combofix's window whilst it's running. That may cause it to stall.
   2. ComboFix may reset a number of Internet Explorer's settings, including making I-E the default browser.
   3. Combofix prevents autorun of ALL CD, floppy and USB devices to assist with malware removal & increase security. If this is an issue or makes it difficult for you - please let me know.
   4. ComboFix disconnects your machine from the internet when it runs. This connection should be automatically restored when ComboFix completes its run. If ComboFix runs into difficulty and terminates prematurely, the connection can be manually restored by restarting your machine.
 5.In case of a severe infection combofix may automatically restart the computer.Don't panic and let it happen.
 6.After scanning combofix will produce a log. Do not click anything until combofix finish making the log.
 7.Make sure all unnecessary processes are closed before scanning with combofix.

PREPARE A HijackThis LOG FILE AFTER THIS STEP


I think that I have made it clear that I am not trained to help with such large networks. The tools we use here are complex and may adversely affect your system. Use them only after proper discussion with your security team.

Also, as awesec suggested your company need to have a disaster recovery plan to deal with such issues.

In case none of the solutions work for you reverting to the latest backups is the best option.

Also, try to follow Dav_Id's suggestion first [/list]

Finally i got the solution from microsoft forefront client security 1.63.471 definition.It is able to clean the files without deleting the infected files....
try the same..

Thanks for all your valuable supports.