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.