I usually set up my SSH autocompletes to read from known_hosts. The problem is that on some systems, like say Debian, the hostnames are hashed for security reasons. So you have to add the following line to your .ssh/config to get the hostnames back into a readable form.
Bash has had this for ages too. Debian comes with it in the "bash-completion" package, for example. People get all excited about trivial enhancements for Bash for the same reasons they don't know about Zsh: The pain isn't great enough for them to actively seek out alternatives.
So why aren't they on by default? Why is the latest Ubunbtu (styled as a user friendly Linux not a purist Linux) still making the clueless "HUH?" noise at me during tab completion because it doesn't have completion-ignore-case on by default? Or automatically showing a list of clashes or cycling through clashes instead of sitting there like a lemon? Both also one line of config somewhere.
Because not enough people care enough to push hard enough for it to change - presumably most of the people who do care don't find having to do apt-get install bash-completion onerous enough to matter.
I downloaded "oh my zsh", never looked back. Of course, I only made it look exactly like fish, which is what I was using, but it's less buggy than fish.
On the flip side a similar script to use a similar technique in .profile to strip out all SSH lines in your history would be a good security measure. That account gets compromised and you wouldn't have a road map of other hosts to connect to. Could remove known_hosts on systems that don't hash the hostnames too. Maybe I really am turning into a grumpy Sa if these are my first thoughts on reading things like this.
I have been using this trick for a while. It is annoying in two ways: first, it includes misspelled hosts. Second, it does not work for scp and sftp. Otherwise, it may save you time.
OP's method would be helpful when the line differs syntactically prior to the hostname e.g. different options, arguments, a pipe into it. Though that case is rare in my own usage.
EDIT [missed the edit window] whoops, I see ctrl-r is "reverse-search-history" (not "history-search-backward"), it matches your input to any part of the history (so the prefix issue doesn't arise). So you could just type the hostname, and it will pick out the most recent line in the history that matches - it needn't be at the beginning of the line. You can hit ctrl-r again to go to a matching line further up.
ctrl-s goes back down again, but not working for me, apparently because my gnome terminal intercepts it before bash's readline sees it, using it for xon/xoff according to http://stackoverflow.com/questions/791765/unable-to-forward-... This "fixes" it (by disabling the STOP feature of the terminal), so ctrl-s works to search down.
Honestly, simply reading `man bash` from start to finish was one of the best things I ever did. I started doing it with all sorts of stuff. May I suggest you start with `man man`?
Then someone told me about `apropos` which is summarized in it's man page as "search the whatis database for strings". Sooo useful. Not nearly as useful as simply reading man pages from start to finish, but I've only got so much spare time.
Reading `man` is the kind of thing you understand after years of hitting hard walls. Even now I still despise it even though I know most of the answers are in it. I think I want something less linear to search into, oh and I'm surely a lazy P*S too.
Or give zsh a try, simply autoload compinit and it will do ssh/sftp auto completions along with a boatload more out of the box.