AUCTeX knows that $ is not special in verbatim environments, but you have to tell it that Verbatim is a verbatim environment by arranging for it to appear in LaTeX-verbatim-environments-local.
If AUCTeX is installed optimally, it already knows, because AUCTeX loads a style hook for each file you load through \usepackage and friends. You may need to tell it to parse your header file with C-c C-n (TeX-normal-mode).
If that's not enough, it means Verbatim was defined in a style file for which AUCTeX doesn't have enough information. You can tell AUCTeX to parse some or all the style files you have installed; see the “Automatic” chapter in the AUCTeX manual.
Sometimes AUCTeX doesn't manage to parse the style file; then you can do this part by hand. The code below assumes that you're getting the Verbatim environment from the fancyvrb package; adapt the name otherwise. Create a file called fancyvrb.el in one of the directories mentioned in TeX-style-path with the following contents (there may be other things worth putting there, I've just adapted alltt.el):
(TeX-add-style-hook
 "fancyvrb"
 (lambda ()
   (LaTeX-add-environments "BVerbatim" "LVerbatim" "SaveVerbatim" "Verbatim")
   (make-local-variable 'LaTeX-indent-environment-list)
   (add-to-list 'LaTeX-indent-environment-list '("BVerbatim" current-indentation))
   (add-to-list 'LaTeX-indent-environment-list '("LVerbatim" current-indentation))
   (add-to-list 'LaTeX-indent-environment-list '("SaveVerbatim" current-indentation))
   (add-to-list 'LaTeX-indent-environment-list '("Verbatim" current-indentation))
   (make-local-variable 'LaTeX-verbatim-regexp)
   (setq LaTeX-verbatim-regexp (concat LaTeX-verbatim-regexp "\\|\\([BL]?\\|Save\\)Verbatim"))
   (add-to-list 'LaTeX-verbatim-environments-local "BVerbatim")
   (add-to-list 'LaTeX-verbatim-environments-local "LVerbatim")
   (add-to-list 'LaTeX-verbatim-environments-local "SaveVerbatim")
   (add-to-list 'LaTeX-verbatim-environments-local "Verbatim")
   (when (and (featurep 'font-latex)
              (eq TeX-install-font-lock 'font-latex-setup))
     (font-latex-set-syntactic-keywords)
     (setq font-lock-set-defaults nil)
     (font-lock-set-defaults))))
(I thought you could also do it manually through file variables, but this turns out not to work, because the font-lock settings are built before the file local variables are initialized, and I don't see a workaround.)