Com o Vim sozinho:
:set path=.,,**
:find foo.txt
O nome do arquivo não pode conter curingas, mas :find
tem conclusão de tabulação.
Como alternativa, existem muitos plugins excelentes que podem fazer isso e muito mais, f.i. Unite , CtrlP , ou fzf .