In case you're using fancyvrb.sty to define your custom environment, you only need to hit C-c C-n and let AUCTeX parse your document. AUCTeX has a sophisticated style file for fancyvrb.sty which takes care of adding your environment to various internal variables. After that, you can do C-c C-e myverTAB RET to include it in your document. AUCTeX will ...
Add your self-defined verbatim environment to LaTeX-indent-environment-list.
Your modified example would look like this:
that LaTeX-fill-region does something.
First verbatim line.
Second verbatim line.
% Local ...