The article doesn't say, so it's worth mentioning that you can type ctrl-R multiple times to search further back into command history.
It's so ingrained I had to actually do it in a shell to know what it was I did.
I can't replicate it now on my test box; it works exactly the way you say it should. It may be a terminal issue; I'm currently on Windows using cygwin to ssh to Linux.