tikz/pgfplot -- always same distance between marks

Similar to Harish's answer but removes the need to plot twice. You basically need to stop the postaction reaching to the legend pictures because that is what is causing the funky mark placement. And that you can do with our good ol' answer to Applying a postaction to every path in TikZ

\documentclass[]{standalone}
\usepackage{pgfplots}
\pgfplotsset{compat=1.11}
\usetikzlibrary{decorations.markings}
\makeatletter
\tikzset{
  nomorepostactions/.code={\let\tikz@postactions=\pgfutil@empty},
  mymark/.style 2 args={decoration={markings,
    mark= between positions 0 and 1 step (1/11)*\pgfdecoratedpathlength with{%
        \tikzset{#2,every mark}\tikz@options
        \pgfuseplotmark{#1}%
      },  
    },
    postaction={decorate},
    /pgfplots/legend image post style={
        mark=#1,mark options={#2},every path/.append style={nomorepostactions}
    },
  },
}
\makeatother

\begin{document}
\begin{tikzpicture}
\begin{axis}[legend style={at={(0.5,0.95)}, anchor=north},
  legend entries={$\exp(x)$,$10\sin(5x)$},
]
\addplot[blue,dashed, domain=0:3,samples=15,mymark={o}{solid}]{exp(x)};
\addplot[red,domain=0:3, dashdotted,samples=200,
           mymark={diamond*}{draw=black,fill=yellow,solid}]{10*sin(deg(5*x))};
\end{axis}
\end{tikzpicture}
\end{document}

You can also add yet another parameter for how many marker you want to have by dividing the total path length to a fixed number. Here I went with 11. (replacing it with a distance is what you wish probably but I put here as an alternative)

with 1 cm mark distance

EDIT For the added style question, the code now gives

Done with MetaPost, with the actual sinus curve. (The legend box is still to be done.) For the markers, is it something like that you wish to obtain?

Note that it is only an adaptation of my answer to a very similar question here: Pgfplot, show mark when distance along the path is reached

Edit The cartouche is here now, with some other (minor) changes.

\documentclass[border=2bp]{standalone}
\usepackage{luamplib}
    \mplibsetformat{metafun}
    \mplibtextextlabel{enable}
    \mplibnumbersystem{double}
\begin{document}
\begin{mplibcode}
% Reimplementation of the `point .. of ..` binary operator
% somewhat bugged in the current metafun format: 
% http://tug.org/pipermail/metapost/2015-March/003065.html
primarydef len on pat = % no outer ( ) .. somehow fails
     (arctime if len>=0 : len else : (arclength(pat)+len) fi of pat) of pat
enddef;

% Parameters
u = 2cm; v = .3cm; pen bigdot; bigdot = pencircle scaled 3bp;
xmin = -.25; xmax = 3.25; ymin = -1; ymax = 22.5;
len = 4bp; nmarks = 20; % length and number of marks

% Function curve
vardef function(expr xmin, xmax, xstep)(text f_x) =
    save x; x := xmin;
    (x, f_x)
    forever:
        hide(x := x + xstep)
        exitunless x <= xmax;
        .. (x, f_x)
    endfor
    if x - xstep < xmax: hide(x := xmax) .. (x, f_x) fi
enddef;

% Exponential and sinusoide curve
path expcurve; expcurve = function(ceiling(xmin), floor(xmax), .1)(exp x) xyscaled (u, v);
path sincurve; sincurve = function(ceiling(xmin), floor(xmax), .1)(10sin x) xyscaled (u, v);

% Space between marks
exp_marksep = arclength expcurve / (nmarks-1);
sin_marksep = arclength sincurve / (nmarks-1);

% Cartouche management
def define_cartouche(text cartouche)(expr pos) = 
    picture cartouche; cartouche = nullpicture;
    numeric _cnt; _cnt = 0;
    def addto_cartouche (suffix cartouche)(expr wd, str) =
        addto cartouche also (image(draw pos - (wd,0) -- pos; 
            drawdot pos - (.5wd, 0) withpen bigdot;
            label.rt(str, pos) withcolor black)
                yshifted -_cnt*\mpdim{\baselineskip});
        _cnt := _cnt + 1;
    enddef;
enddef;

beginfig(1);
    define_cartouche(box)((2u, 20v));

    % Curves and marks
    drawoptions(withcolor blue); draw expcurve;
    for i = 0 upto nmarks-1:
        %drawdot point (arctime (i*exp_marksep) of expcurve) of expcurve withpen bigdot; 
        draw point (i*exp_marksep) on expcurve withpen bigdot;      
    endfor
    addto_cartouche(box, .5cm, "$\exp x$");

    drawoptions(withcolor red); draw sincurve;
    for i = 0 upto nmarks-1:
        %draw point (arctime (i*sin_marksep) of sincurve) of sincurve withpen bigdot; 
        draw point (i*sin_marksep) on sincurve withpen bigdot;
    endfor
    addto_cartouche(box, .5cm, "$10\sin x$");

    % Axes and labels
    drawoptions();
    draw ((xmin, ymin) -- (xmax, ymin) -- (xmax, ymax) -- (xmin, ymax) -- cycle) xyscaled (u, v);  
    for i = 0 upto 3:
        draw (u*i, ymin*v) -- (u*i, ymin*v+len);
        draw (u*i, ymax*v) -- (u*i, ymax*v-len);
        label.bot(decimal i, (i*u, ymin*v));
    endfor;  
    for j = 0 step 5 until 20:
        draw (xmin*u, j*v) -- (xmin*u + len, j*v);
        draw (xmax*u, j*v) -- (xmax*u - len, j*v) ;
        label.lft(decimal j, (xmin*u, j*v));
    endfor;

    draw bbox box enlarged 2bp; draw box;

endfig;
\end{mplibcode}
\end{document}

If a manual solution is sufficient for your usage, you can use the mark repeat=<n> key to draw only every n th mark. Here, I've added 1 to each of your samples settings so that things work out in nice integers:

\documentclass[tikz,border=1mm]{standalone}
\usepackage{pgfplots}
\usetikzlibrary{decorations.markings}
\pgfplotsset{compat=1.11}

\begin{document}
\begin{tikzpicture}
\begin{axis}[]
\addplot[
  blue,
  domain=0:3,
  samples=101,
  mark=*,
  mark repeat=5, % calculated using (101-1)/(21-1) = 5
  ]
{exp(x)};
\addlegendentry{exp(x)};

\addplot[
  red,
  domain=0:3,
  samples=21,
  mark=diamond
  ]
{4*x};
\addlegendentry{10 sin(x)};

\end{axis}
\end{tikzpicture}
\end{document}