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.
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop