Virus that tries to brute force attack Active Directory users (in alphabetical order)?

Sorry, I've no idea what this is, however, you have more important issues right now.

How many machines are doing this? Have you disconnected them all from the network? (and if not, why not?)

Can you find an evidence of any domain accounts being compromised (especially domain admin accounts)

I can understand you not wanting to build your desktops again, but unless you do, you can't be sure you'll clean the machines.

First steps:

• Ensure complex passwords are enabled on your domain
• set a lock out policy - this will cause you problems if you still have scanning machines but this is better than more accounts being compromised
• Isolate a known bad machine, is it trying to talk to the outside world? You need to block this across your network at your gateway
• Attempt to isolate all known bad machines.
• Monitor for more scanning machines.
• Force all your users to change their password, check all your service accounts.
• Disable any accounts no longer in use.
• Check your group memberships on servers and DCs (Domain Admins, Administrators, etc)

Next you need to perform some forensics on your known bad machines to try and trace what has happened. Once you know this, you stand a better chance of knowing what the scope of this attack is. Use root kit revealer, perhaps even image the hard disk before you destroy any evidence. Linux Live CDs with NTFS support can be very useful here, as they should allow you to find what a root kit could be hiding.

Things to consider:

• Do you have a standard local admin (weak) password on all the workstations?
• Do your users have admin rights?
• Are all domain admins using separate accounts for DA activities? Consider setting restrictions on these accounts (e.g. workstations you can log on to).
• You don't give any info about your network. Do you have any publicly exposed services?

Edit: Trying to give more info is difficult, as it really depends upon what you find, but having been in a similar situation several years ago, you really need to distrust everything, especially machines and accounts that you know to be compromised.

It could be anything from L0phtCrack to THC-Hydra or even a custom-coded application, though your AV solution should have picked up the well-known apps.

At this point, you need to identify all the systems infected, quarantine them (vlan, etc), and contain and eradicate the malware.

Have you contacted your I.T. Security team yet?

Finally, I understand you not wanting to rebuild, but at this point, (with the little data you have given), I would say that the risk warrants rebuilds.

-Josh