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.
