You could combine Bash's existing history and history searching features. Press Ctrl-R to begin incremental reverse searching, then start typing the part of the path most likely to be unique.
You can keep typing letters until you end up back at the most recent cd command involving that directory, or you can press Ctrl-R again to jump back in history to the next newest command matching what you've typed so far.
I do this all the time.
Actually, I take it a step further. Once I start discovering sequences of commands worth keeping in history but not worth committing to a shell script, I start chaining them up with && and ; combinators so I can reverse-search for a substring of that one long command, hit Enter and run the whole sequence at once.
For example, here's how I build and run one of my programs during development:
$ ( cd .. ; make install ) && ./start_my_program
I do this from the install directory, which is underneath the top-level source directory. By wrapping the cd, build and install part in a sub-shell, I ensure that no matter what happens during this process, I end up back in my normal shell with nothing changed. Only if that succeeds (&&) do I start the built and installed program. I can find this in my history with just a Ctrl-R then sta, that being all I usually need to uniquely find this command sequence.
Another example of how I use this is the sequence that goes into building RPMs for this same program. Most of the tedious work is in shell scripts, but there are still a few commands I'd normally have to type to do all the work of building and deploying the built RPMs, which I now rarely have to re-type, because Bash keeps it in history for me.
Combine all this with export HISTSIZE=bignum and shopt histappend and you have just built an elephantine command memory.
Another solution I coded up once is in my answer to another question here. It might have to be tailored for your purposes, and it only handles cd commands, whereas the history searching option works everywhere and for every command.