i've written a plugin as well. it's extremely simple: it uses find (or globpath() if you do not like external dependencies) to build a local cache. matching isn't approximate but you get results on partial matches and can browse files in directories (something i really missed in some other solutions).
i recorded a quick screencast: http://pipsq.com/s.mov
note that i'm matching against the linux source; searching smaller source trees should be a lot faster.
you can try it out by downloading the following files:
http://github.com/strange/dotfiles/blob/master/.vim/plugin/p...
http://github.com/strange/dotfiles/blob/master/.vim/autoload...
launch with :Pyxis or create a map:
noremap e :Pyxis
noremap E :PyxisUpdateCache