I'm experiencing this as well.
In my project we are using Hibernate Validator as JSR 303 implementation.
I'm not defining anything else special as Spring is picking up this automatically and creating the right beans internally.
I suspect this is caused by Bean Validation's iteration over constraints, assumably in a HashSet with hash order over annotation types which is rather unpredictable. From that perspective, it's a problem to be reported to Hibernate Validator and the Bean Validation specification.