Why not just use, say, an actual (i.e. backtrack-free, DFA-based) regular expression library?
Vim uses an NFA style engine and it was obvious to me that backtracking with these patterns would be an issue. Since we went to such great lengths to provide the most accurate regular expression highlighting possible for Clojure, which is pretty damn accurate, I figured we might as well try to make it performant. It turns out our efforts were not in vain.
Have a look at this pull request: https://github.com/guns/vim-clojure-static/pull/28.