Is there a way to avoid a Brute Force Attack from locking all the user accounts in the User Store?
During a brute force attack repeated attempting to login as the same user can lock the user account. And since these are list driven, multiple accounts can be locked. More advanced forms use a regex to build usernames similar to known ones also leading to more accounts being locked.
To stop a Brute Force Attack from the internet against your User Store, you should first filter requests by IP's on:
Assuming the source if from the same IP or block of IPs. Work with the network security team to identify this and block it.
With SiteMinder, the Password Policy can be set to re-enable the User's account after a period of time by the "Expiration" Tab of the Password Policy. While this doesn't stop the attack, it will at least allow the users a chance to continue working.