How to pass an optional argument to an environment with verbatim content?

I can answer what is happening, but I don't have a fix for you.

What is happening is that when looking for the optional argument, the ^^M that got inserted by TeX at the end of the line is tokenized. Since TeX is in state M, and ^^M has category code 5, this is turned into a space token. LaTeX's \kernel@ifnextchar gobbles the space and keeps looking for a nonspace character. It finds \relax which isn't [ so it expands to \\Row[{}].

\\Row[#1] has the begin environment code. \VerbatimOut changes the category code of ^^M to active and then looks for an active ^^M to follow. However, that was already tokenized with catcode 5 and then swallowed. Since it finds \relax, it complains.

Edit:
If, like me, you have a hard time seeing how the space is getting swallowed by tracing this, the key is this line.

\reserved@c  ->\futurelet \@let@token \@ifnch
            ^

The extra space that I marked with the caret is part of the definition of \@xifnch:

\def\:{\@xifnch} \expandafter\def\: {\futurelet\@let@token\@ifnch}

Edit 23:
Sorry, I should have put a bit a thought into this. This isn't hard to fix. My original comments give the hint of how to fix it, just make ^^M active! A better solution is to reinsert an active ^^M character in the case that there is no optional argument. That way the optional argument can be on the next line as in the third use of \begin{Row} below.

\documentclass{minimal}
\usepackage{listings,fancyvrb}

\begingroup
\catcode`\^^M\active%
\global\def\activeeol{^^M}%
\endgroup
\makeatletter
\newenvironment{Row}{%
        \@ifnextchar[\Row@\Row@noargs
}{%
        \end{VerbatimOut}%
        \lstinputlisting{\jobname.tmp}%
}
\def\Row@[#1]{%
        #1\par
        \VerbatimEnvironment
        \begin{VerbatimOut}{\jobname.tmp}%
}
\def\Row@noargs#1{%
        \edef\temp{[]\activeeol\string#1}%
        \expandafter\Row@\temp
}
\makeatother
\begin{document}
\begin{Row}[optional argument]
\relax
\end{Row}

\begin{Row}
\relax
\end{Row}

\begin{Row}
[Another optional argument]
\relax
\end{Row}
\end{document}

EDIT: TH.'s answer is much simpler. The one below should depend less on the details of the implementation of \VerbatimEnvironment, but that's the only good thing about it.

I propose the following code. The idea is to make a new environment (which I called Row, renaming the old Row to oldRow) check for an optional argument "by hand", and write the relevant thing to a file. Then the file (\jobname.row) is read so that fancyvrb can happily set the relevant catcodes.

All this can probably be done using \scantokens, but I am still quite confused about newlines inside \scantokens.

I also added *#1* to your definition of the environment: this way, we can check what is going on with the optional argument.

\documentclass{minimal}
\usepackage{listings,fancyvrb}

\newenvironment{oldRow}[1][]
{*#1*\VerbatimEnvironment
  \begin{VerbatimOut}{\jobname.tmp}}
  {\end{VerbatimOut}\lstinputlisting{\jobname.tmp}}


\begin{document}

% ==============================================
\makeatletter
\newwrite\RowWrite

\newcommand{\makeallother}{%
  \count0=0\relax 
  \loop\relax 
  \catcode\count0=12\relax 
  \advance\count0 by 1\relax 
  \ifnum\count0<256\relax
  \repeat\relax}

\newenvironment{Row}{%
  \makeallother
  \futurelet\next
  \Row@aux@i}{}

\newcommand{\Row@aux@i}{%
  \def\Row@optional@arg{}%
  \ifx[\next
  \expandafter\Row@grab@until@bracket
  \else
  \expandafter\Row@grab@until@end
  \fi}

\def\Row@grab@until@bracket[#1]{%
  \def\Row@optional@arg{#1}\Row@grab@until@end}

% First expand the \csname...\endcsname,
% then the \string, then the \def.
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\Row@grab@until@end
\expandafter\expandafter\expandafter#%
\expandafter\expandafter\expandafter1%
\expandafter\string\csname end{Row}\endcsname{%
  \begingroup%
  \newlinechar=`\^^M%
  \immediate\openout\RowWrite\jobname.row\relax%
  \immediate\write\RowWrite{%
    \string\begin{oldRow}[\Row@optional@arg]#1\string\end{oldRow}%
  }%
  \immediate\closeout\RowWrite%
  \endgroup%
  \end{Row}\input{\jobname.row}%
}

\makeatother
% ==============================================

\begin{Row}
  \relax
  \relax
\end{Row}

\begin{Row}[option]
  \relax
  \relax
\end{Row}


\end{document}

As I learned from TH in the comments to his answer, the real culprit is the TeX primitive \futurelet that is used to detect if there's an optional argument. If there is none, then the end-of-line character ^^M (with usually has catcode 5) gets tokenized by the \futurelet, meaning that the catcode can't be changed anymore. Now \begin{VerbatimOut} changes the catcode of ^^M to 13 (active), but this has no effect on the ^^M that is already tokenized, and one gets the error.

Here's another solution along the lines of the definition of fancyvrb's \FV@Environment. Unlike TH's solution, it does not allow the optional argument to start on the next line (but it does allow spaces before the [). However, this is maybe the right behaviour: Who knows; the code could start with a [. Thus, when you compile the code below, then [Another optional argument] will be the first line of the third piece of code.

\documentclass{minimal}
\usepackage{listings,fancyvrb}

\makeatletter
\newenvironment{Row}{%
    \catcode`\^^M=\active
    \@ifnextchar[%
        {\catcode`\^^M=5 \Row@}
        {\catcode`\^^M=5 \Row@[]}
}{%
    \end{VerbatimOut}%
    \lstinputlisting{\jobname.tmp}%
}
\def\Row@[#1]{%
    *#1*\par
    \VerbatimEnvironment
    \begin{VerbatimOut}{\jobname.tmp}%
}
\makeatother
\begin{document}
\begin{Row}[optional argument]
\large a
\end{Row}

\begin{Row}
\large a
\end{Row}

\begin{Row}
[Another optional argument]
\large a
\end{Row}
\end{document}