And that's exactly what denyhosts is for. You'll see this line a few initial times, then the banhammer springs into action.

(It's fully configurable - the number of failed attempts, the length of the autoban, etc.)

Unfortunately one attempt is enough when there's a pre-auth vulnerability. Your ban-hammer doesn't help you there.

until one of the millions of other compromised IPs begins hammering your machine minutes later..

That's the whole point. The ban-hammer in this case is automatic and will ban that one too after five attempts or whatever.

You're missing the point. One attempt is enough when there's a pre-auth exploit.

it still doesn't prevent your logs getting filled up with crap is my point.

Preventing logs from filling up is quite a cosmetic issue. Making the box hard to crack is certainly more relevant.

Note that I'm not advocating against a port change; just saying that it's the very last of available options, as it's essentialy security-by-obscurity, and thus only gives you a feeling of higher security (due to less spam in the logs).

Making security logs usable can (note the word) be a very important part of a security setup. Lots of people don't have the bandwidth to pay attention to noisy log files to look for anomalies.

There is also ssh-faker: http://www.pkts.ca/ssh-faker.shtml

Which would prevent even that first password failure attempt from occurring.

Sending a password over telnet seems like a bad idea..