I'm looking actually for something similar to Deft, only for Vim. Does anyone know of any with which he/she has had good experiences?
Check out vim-notes: https://github.com/xolox/vim-notes
It's a fairly sophisticated, and yet simple, note-taking platform. It doesn't have Deft's incremental search etc (I've used Emacs, so I know the features), but therefore you can tag your notes very comfortably, use auto-complete and, of course, search through the files. (The search is Python-based and so somewhat faster than vim-grep).
Just like in Deft, your notes are stored in one folder.
BTW, I think I found it while struggling with the exact same question as yours -- having recently moved to Vim, I needed an alternative to Deft.
UPDATE: Also, you could check out the CtrlP plugin: https://github.com/kien/ctrlp.vim. An excellent tool that allows you to search file names incrementally. It's very fast, nicely customizable and pure vimscript (so no external dependencies are needed).
Many months later: Also, there's unite.vim, which might have some potential as "poor man's Notational Velocity in Vim". At least people appear to be using it to replace both ctrlp.vim and ack.vim/grep.vim with one plugin. Looks very interesting indeed.
Even more later: Now there's also nvim, a direct clone of Notational Velocity. Looks good but takes some time to get used to in my experience: https://github.com/cwoac/nvim
Almost another year later: microViche might also be of interest here. Not quite like Deft, but an one of a kind approach to note taking or writing in Vim in my opinion. Basically it lets you link lines/paragraphs in different files, display all these links as a map (cool!) and have all files simultaneously open. So you can browse your documents as if you had them open in a microfiche reader, "panning and zooming through text" as the author says, and writing many documents in parallel. He also has a screencast for the plugin. https://github.com/q335r49/microviche
There are other scripts on vim.org but these ones are the closest, I think.