So I have 3 terminal servers which are being attacked. This person, or group seems to know our employee naming convention because he is using all the correct names which is what scares me. We have strong passwords, but at this rate, I do not know how long they will hold up.  I've changed the ports on the terminal servers, but that didn't stop them long. I have a security policy set to lock the account after 3 unsucessful tries, but my logs are showing these guys have tried over 20K times to login over the past week. When I attempt to login with bad passwords using various rdp clients I get disconnected and locked out for 30 minutes after 3 unsucessful attempts... so what is allowing these guys to continue to brute force 1000's of times a night?

I am afraid that I don't have much knowledge about how to handle these types of attacks against (Windows) terminal servers, but I do have a fair amount against SSH servers which is similar in many ways.  I am not sure why your policy isn't working.  Are the full attempts or are they just connect-disconnect sessions in an attempt to cause a buffer overflow?  It sounds like they are using some variation on the protocol to avoid this type of blocking by not triggering the rules.

The first thing I would suggest is seeing if you can use a firewall to buy you some time.  Obviously you are thinking along the same lines, from your security policy comment.  In the *nix environment, there is a very useful tool called fail2ban, which is an adaptive firewall program that blocks attempts like this.  While there doesn't seem to be a direct version for Windows, this link has a possible suggestion.

In regards to firewall, I would also look to see if you can find the network range, possibly even using the AS number that they are connecting from and block those IP ranges.  The problem is you appear to be facing an intelligent attacker that is using port scans to find your services and may have inside information.  I would expect them to adapt and come at you from somewhere else.

The ultimate answer I would suggest is to get away from using username + passwords for your authentication.  Instead use RSA key based authentication as it is simply not vulnerable to this type of attack.

You might also want to contact your ISP, since you seem to have a deliberate attacker.  They may be able to help.