This was talked before in SF. iptables
changed the way it accept parameters. Now the bang should be before the parameter, so your lines becomes this:
-A INPUT -p tcp --dport 22 ! -s 10.0.0.0/8 -m state --state NEW -m recent --set --name SSH
-A INPUT -p tcp --dport 22 ! -s 10.0.0.0/8 -m state --state NEW -m recent --update --seconds 600 --hitcount 25 --rttl --name SSH -j DROP
And yes, every blog in internet is wrong.