This may not be exactly what you want, but I found this code snippet for your bashrc file on some "tips & tricks" thread a while back that's supposed to show you all the previous entries for a command in your history. However for some reason it never worked for me. Maybe it'll do something for you.
# user added binds to special keys:
# <Alt>+w to show all possible completions for a command from history.
bind '"\M-w"':"\"\C-k\C-ahistory | grep '^ *[0-9]* *\C-e.'\C-m\""
In the meantime, at least there's always <crtl>-r and <crtl>-s for searching backwards and forwards through your history.
If you know something about scripting, there should be an /etc/bash_completion file that has all sorts of code controlling what gets completed and what doesn't. Don't ask me how it all works though.