As long as you protect access to the rule mutators, you shouldn't have any threading issues.
We use the PasswordValidator in a multi-threaded environment without any issues.
Of course, if you implement your own rules, you'll need to ensure that the #validate implementation doesn't change the state of your rule.
--Daniel Fisher