I'll just show my solution (again):
/etc/sysconfig/iptables:
:ssh - [0:0]
-A INPUT -p tcp --dport 12345 -m recent --name SSHAUTH --set -A INPUT -p tcp --dport ssh -m state --state NEW -j ssh
-A ssh -m recent --name SSHAUTH --update --seconds 43200 -j ACCEPT -A ssh -s GOOD_IP/MASK -j ACCEPT ... -A ssh -j REJECT --with-with tcp-reset
Which lets local networks (and any special hosts you specify like computers you often use) connect to ssh (GOOD_IP/MASK) and requires any other machine to first issue any request to a random high port (here 12345, use something more random) before ssh is even let through the firewall.
Depends on your users. In my experience users can be educated :)
Cheers, MaZe.