How to create two environments that refer to each other in the page margin?

Question

I would like to create two environments: one for exercises and one for their solutions. Each exercise should refer to the page of its corresponding solution and vice versa. The problem is not quite ``symmetric'' as the label of a solution should be equal to the label of the respective exercise. So far so good. There is one more requirement: I would like to print the references (of exercises to solutions and of solutions to exercises) in the page margins. As you can see in the MWE below, the margin note is not vertically aligned with the exercise/solution environment (rather with the first row of the body of the environment. I tried to incorporate the \marginnote{} calls as an argument to the exercise/solution environment, but didn't manage to get it to work.

How can this be done?

\documentclass{scrartcl}

\usepackage[T1]{fontenc}
\usepackage[american]{babel}
\usepackage{amsthm}
\usepackage{marginnote}

\newtheoremstyle{exstyle}%
{0.5em}% space above
{0.5em}% space below
{}% body font
{}% indent amount
{\sffamily\bfseries}% head font
{}% punctuation after head
{\newline}% space after head
{\thmname{#1}\ \thmnumber{#2}\ \thmnote{#3}}% head spec
\theoremstyle{exstyle}% activate style
\newtheorem{exercise}{Exercise}[section]

\newtheoremstyle{solstyle}%
{0.5em}% space above
{0.5em}% space below
{}% body font
{}% indent amount
{\sffamily\bfseries}% head font
{}% punctuation after head
{\newline}% space after head
{\thmname{#1}\ \ref{#2}\ \thmnote{#3}}% head spec; obviously, the `\ref{#2}` fails...
\theoremstyle{solstyle}% activate style
\newtheorem{solution}{Solution}

\begin{document}
\begin{exercise}[(Exercise title)]\label{ex}\marginnote{Sol.\ on p.~\pageref{sol}}
  This is the exercise
\end{exercise}
\clearpage
\begin{solution}[(Solution title)]\label{sol}\marginnote{Ex.\ on p.~\pageref{ex}}
  This is the solution
\end{solution}
\end{document}

UPDATE

One approach I tried is to adapt the proof environment for the solutions; see below. This puts the margin note at the right vertical level, but requires to introduce the newlines (after the solution header) by hand. Not sure if there's a more elegant approach...

\documentclass{scrartcl}

\usepackage[T1]{fontenc}
\usepackage[american]{babel}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{enumitem}
\usepackage{marginnote}

% Exercise
\newtheoremstyle{exstyle}%
{0.5em}% space above
{0.5em}% space below
{}% body font
{}% indent amount
{\sffamily\bfseries}% head font
{}% punctuation after head
{\newline}% space after head
{\thmname{#1}\ \thmnumber{#2}\ \thmnote{#3}}% head spec
\theoremstyle{exstyle}% activate style
\newtheorem{exercise}{Exercise}[section]

% Solution (adapted from proof environment)
\makeatletter
\newenvironment{solution}[2][]{\par
  \pushQED{\qed}%
  \normalfont\topsep6\p@\@plus6\p@\relax
  \trivlist
\item[\hskip\labelsep\sffamily\bfseries Solution~\ref{#2}\ #1]%
    \marginnote{Ex.\ on p.~\pageref{#2}}\ignorespaces%
}{%
  \popQED\endtrivlist\@endpefalse
}
\makeatother

\begin{document}
\begin{exercise}[(Exercise title)]\label{ex1}\marginnote{Sol.\ on p.~\pageref{sol1}}
  This is the exercise
\end{exercise}
\begin{solution}[(Solution title)]{ex1}\label{sol1}\\
  This is the solution
\end{solution}

\begin{exercise}[(Exercise title)]\label{ex2}\marginnote{Sol.\ on p.~\pageref{sol2}}
  \vspace{-\baselineskip}
  \begin{enumerate}
  \item Item 1
  \end{enumerate}
\end{exercise}
\begin{solution}[(Solution title)]{ex2}\label{sol2}
  \begin{enumerate}
  \item Item 1
  \end{enumerate}
\end{solution}
\end{document}

UPDATE 2

This shows what I would like to achieve (now with two 'proof-like' environments). As David pointed out here this is normally not what one wants (since one leaves vertical mode)

\documentclass{scrartcl}

\usepackage[T1]{fontenc}
\usepackage[american]{babel}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{etoolbox}
\usepackage{enumitem}
\usepackage{marginnote}

\setlist{
  align=left,
  labelsep=*,
  leftmargin=*,
  topsep=1mm,
  itemsep=0mm
}

% Exercise
% Note: One has to provide \\ by hand in order to get the linebreak after the
%       exercise head (unless itemize/enumerate follows)
\newcounter{counter}% exercise counter
\makeatletter
\newenvironment{exercise}[2][]{\refstepcounter{counter}\par
  \normalfont\topsep6\p@\@plus6\p@\relax
  \trivlist
\item[\hskip\labelsep\sffamily\bfseries Exercise~\thecounter\ #1]%
    \marginnote{Sol.\ on p.~\pageref{#2}}\ignorespaces
}{%
  \endtrivlist\@endpefalse
}
\makeatother

% Solution
% Note: One has to provide \\ by hand in order to get the linebreak after the
%       exercise head (unless itemize/enumerate follows)
\makeatletter
\newenvironment{solution}[2][]{\par
  \pushQED{\qed}%
  \normalfont\topsep6\p@\@plus6\p@\relax
  \trivlist
\item[\hskip\labelsep\sffamily\bfseries Solution~\ref{#2}\ #1]%
    \marginnote{Ex.\ on p.~\pageref{#2}}\ignorespaces
    \ignorespaces%
}{%
  \popQED\endtrivlist\@endpefalse
}
\makeatother

\begin{document}
\begin{exercise}[(Exercise title)]{sol1}\label{ex1}\\
  This is the exercise
\end{exercise}
\begin{solution}[(Solution title)]{ex1}\label{sol1}\\
  This is the solution
\end{solution}

\begin{exercise}[(Exercise title)]{sol2}\label{ex2}
  \begin{enumerate}
  \item Item 1
  \end{enumerate}
\end{exercise}
\begin{solution}[(Solution title)]{ex2}\label{sol2}
  \begin{enumerate}
  \item Item 1
  \end{enumerate}
\end{solution}
\end{document}

Answer 1

Only a partial solution for the mutual reference: You need autogenerated labels.

In my point of view, the exercise/solution environments should be wrapped into other environments, which do some setup, especially the \marginnote alignment.

\documentclass{scrartcl}

\usepackage[T1]{fontenc}
\usepackage[american]{babel}
\usepackage{amsthm}
\usepackage{marginnote}

\newtheoremstyle{exstyle}%
{0.5em}% space above
{0.5em}% space below
{}% body font
{}% indent amount
{\sffamily\bfseries}% head font
{}% punctuation after head
{\newline}% space after head
{\thmname{#1}\ \thmnumber{#2}\ \thmnote{#3}\label{ex:\number\value{exercise}}}% head spec
\theoremstyle{exstyle}% activate style
\newtheorem{exercise}{Exercise}[section]

\newtheoremstyle{solstyle}%
{0.5em}% space above
{0.5em}% space below
{}% body font
{}% indent amount
{\sffamily\bfseries}% head font
{}% punctuation after head
{\newline}% space after head
{\thmname{#1}\ \ref{ex:\number\value{exercise}}\ \thmnote{#3}\label{sol:\number\value{exercise}}}% head spec; obviously, the `\ref{#2}` fails...
\theoremstyle{solstyle}% activate style
\newtheorem{solution}{Solution}

\begin{document}
\begin{exercise}[(Exercise title)]\label{ex}\marginnote{Sol.\ on p.~\pageref{sol}}
  This is the exercise
\end{exercise}
\clearpage
\begin{solution}[(Solution title)]\label{sol}\marginnote{Ex.\ on p.~\pageref{ex}}
  This is the solution
\end{solution}


\begin{exercise}[(Foo question)]\marginnote{Sol.\ on p.~\pageref{sol:\number\value{exercise}}}
  This is the exercise
\end{exercise}
\clearpage
\begin{solution}[(foo solution)]\marginnote{Ex.\ on p.~\pageref{ex:\number\value{exercise}}}
  This is the solution
\end{solution}

\end{document}

Edit Wrapper commands which mimic the theorem and provide correct links/labels etc.

\documentclass{scrbook}

\usepackage{marginnote}
\usepackage{xparse}

\usepackage{hyperref}

\newcounter{exercise}
\newcounter{solution}


\newwrite\allmysolutions

\AtBeginDocument{%
  \immediate\openout\allmysolutions=\jobname.sol
}

\newcommand{\CloseSolutions}{%
  \immediate\closeout\allmysolutions
}

\newcommand{\InputSolutions}{%
  \InputIfFileExists{\jobname.sol}{}{}%
}


\NewDocumentCommand{\DoExercise}{O{}+m+m+o}{%
  \newpage% Just for demo of pages etc. 
  \refstepcounter{exercise}\label{ex:\number\value{exercise}}
  Exercise (#2) \theexercise \IfValueTF{#4}{\marginnote{Sol.\ on p.~\pageref{sol:\number\value{exercise}}}}{\refstepcounter{solution}}

  #3
  \IfValueT{#4}{%
    \immediate\write\allmysolutions{%
      \string\newpage% Just for demo
      \string\refstepcounter{solution}\string\label{sol:\number\value{exercise}}^^J%
      Solution (Solution of #2) \string\thesolution \unexpanded{\marginnote{Exercise.\ on p.~\pageref{ex:\number\value{exercise}}}}

      \unexpanded{#4}
      \vskip\baselineskip
    }
  }
  \vskip\baselineskip
}


\begin{document}

\DoExercise{Einstein}{$E = mc^2$}[Yes, it's true]


\DoExercise{Heisenberg}{Proof $\Delta x\Delta p \ge \hbar$}[Yes, it's true -- it's science]

\CloseSolutions
\InputSolutions

\end{document}