Unfortunately MacVim does not show up in Spotlight searches. Is this normal?
It's actually a symlink and not an alias. Spotlight indexes symlinks to files that are treated as system files, but it doesn't show them in the GUI. It does show aliases though, so you could just command-option-drag /usr/local/Cellar/macvim/*/MacVim.app to /Applications from Finder.
Or convert the symlinks to aliases:
brew linkapps; find ~/Applications -type l | while read f; do osascript -e "tell app \"Finder\" to make new alias file at POSIX file \"/Applications\" to POSIX file \"$(/usr/bin/stat -f%Y "$f")\""; rm "$f"; done
Or if you use Alfred, it can be set to include applications in /usr/local/Cellar in the default search results.