ctrl-r does a fuzzy search in the history and provides most of what I want out of the box. I wonder why this hadn't been mentioned yet.