Ich habe aus dem Beispiel mal die überflüssigen Optionen rausgenommen und das Zeichnen des zweiten Plots zunächst in blau sowie das `forget plot` bei dem roten entfernt. Mag sein, dass das alles irgendeinen Sinn hatte, aber ich verstehe ihn nicht und damit gibt es in der Legende dann wenigstens tatsächlich eine rote Linie.
![alt text][1]
Code:
Du kannst am Ende eines Plots einen Node angeben und mit der Option `pos` festlegen, wo dieser relativ zum Plotpfad plaziert wird. Du kannst auch mehrere Nodes angeben:
    \addplot ...
        node[pos=.75,draw=black,fill=white,inner sep=11pt]{}
        node[pos=.75,circle,fill,inner sep=6pt,opacity=.5]{};
Wenn Du mehrere dieser Bildchen brauchst und die einheitlich sein sollen, kann man sich dafür ein `pic` definieren und das wie einen Node einfügen.
    \documentclass{article}
    \usepackage{pgfplots}
    \pgfplotsset{compat=newest}
    
    \newbox\mybox
    \newcommand{\tikzBox}[2][\mybox]{\sbox#1{\pgfinterruptpicture#2\endpgfinterruptpicture}}
    
    \tikzset{
      kreisbox/.pic={
        \node(rahmen)[draw=black,fill=white,inner sep=11pt]{};
        \node[circle,fill,inner sep=6pt,opacity=.5]{};}
    }
    
      
    \begin{document}
    \begin{tikzpicture}
    \newbox\caseI
    \newbox\caseII
    \tikzBox[\caseI]{\tikz\pic[blue]{kreisbox};}
    \tikzBox[\caseII]{\tikz\pic[red]{kreisbox};}
    \begin{axis}[%
      width=4.521in,
      height=3.566in,
      at={(0.758in,0.481in)},
      scale only axis,
      xmin=0,
      xmax=6,
      ymin=0,
      ymax=900,
      legend style={column sep=5pt,legend cell align=left,align=left}
    ]
    \addplot [color=blue] table[row sep=crcr]{%
        0   1\\
        1   2.71828182845905\\
        2   7.38905609893065\\
        3   20.0855369231877\\
        4   54.5981500331442\\
        5   148.413159102577\\
        6   403.428793492735\\
    }node[pos=.75]{\usebox\caseI};
    \addlegendentry{\scalebox{.5}{\usebox\caseI}}
    \addlegendentry{\scalebox{.5}{\usebox\caseII}}
}pic[pos=.75]{kreisbox};
    \addplot [color=red] table[row sep=crcr]{%
        0   2\\
        1   5.43656365691809\\
        2   14.7781121978613\\
        3   40.1710738463753\\
        4   109.196300066288\\
        5   296.826318205153\\
        6   806.85758698547\\
    }pic[pos=.75]{kreisbox};
    \end{axis}
    \end{tikzpicture}%
    \end{document}
ergibt
![alt text][1]
Wenn die Markierungen auch als Beschreibung in die Legende sollen, dann ist es besser sie in einer Box zu speichern, siehe auch [Wie kann ich Bilder in Legende eines Diagramms einfügen?][2].
    \documentclass{article}
    \usepackage{pgfplots}
    \pgfplotsset{compat=newest}
    
    \newbox\mybox
    \newcommand{\tikzBox}[2][\mybox]{\sbox#1{\pgfinterruptpicture#2\endpgfinterruptpicture}}
    
    \tikzset{
      kreisbox/.pic={
        \node(rahmen)[draw=black,fill=white,inner sep=11pt]{};
        \node[circle,fill,inner sep=6pt,opacity=.5]{};}
    }
    
      
    \begin{document}
    \begin{tikzpicture}
    \newbox\caseI
    \newbox\caseII
    \tikzBox[\caseI]{\tikz\pic[blue]{kreisbox};}
    \tikzBox[\caseII]{\tikz\pic[red]{kreisbox};}
    \begin{axis}[%
      width=4.521in,
      height=3.566in,
      at={(0.758in,0.481in)},
      scale only axis,
      xmin=0,
      xmax=6,
      ymin=0,
      ymax=900,
      legend style={column sep=5pt,legend cell align=left,align=left}
    ]
    \addplot [color=blue] table[row sep=crcr]{%
        0   1\\
        1   2.71828182845905\\
        2   7.38905609893065\\
        3   20.0855369231877\\
        4   54.5981500331442\\
        5   148.413159102577\\
        6   403.428793492735\\
    }node[pos=.75]{\usebox\caseI};
    \addlegendentry{\scalebox{.5}{\usebox\caseI}}
    \addlegendentry{\scalebox{.5}{\usebox\caseII}}
    \addplot [color=red] table[row sep=crcr]{%
        0   2\\
        1   5.43656365691809\\
        2   14.7781121978613\\
        3   40.1710738463753\\
        4   109.196300066288\\
        5   296.826318205153\\
        6   806.85758698547\\
    }node[pos=.75]{\usebox\caseII};
    
    \end{axis}
    \end{tikzpicture}%
    \end{document}
ergibt
![alt text][3]
  [1]: http://texwelt.de/wissen/upfiles/tw_picaufplot.png
  [2]: http://texwelt.de/wissen/antwort_link/15392/
  [3]: http://texwelt.de/wissen/upfiles/tw_legendenbilder.png