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.