Not being satisfied with side-effects of evil-symbol-word-search or having to apply (modify-syntax-entry) explicitly to every mode, I found that apparently minor mode hooks are run after major mode syntax table is created. That means you can add a hook to modify syntax table to evil-mode hook and it should just work.
(defun myhook-evil-mode ()
(unless (or (eq major-mode 'special-mode) (minibufferp))
;; make underscore part of a word
(modify-syntax-entry ?_ "w")))
(add-hook 'evil-local-mode-hook 'myhook-evil-mode)
Maybe not optimal as it's executed every time a new buffer is created, but shouldn't matter in this case. What does though is that this allowed me to get rid of a humongous 49 lines paragraph that was modifying syntax table of every possible mode I got to work with.