I remember when I was trying to get my first validation project working, it seemed like enabling this was a big mystery. In the end, all I had to do was enable <mvc:annotation-driven> + all the things you said you did. I haven't looked but I suspect that this tag actually enables the validator bean you mentioned.
subject: Cannot get basic Spring validation to work. Why?