How to prevent Beamer from repeatedly expanding macros in \frametitle when frame-breaking

You can use the counter \beamer@autobreakcount and do the stepping only if this counter has a less than 2 (it will be normally zero, but it becomes 1 when allowframebreaks is issued).

\documentclass[t]{beamer}
\let\Tiny=\tiny

\newcounter{mycounter}

\makeatletter
\newcommand\exercise{%
  \ifnum\beamer@autobreakcount<2
    \refstepcounter{mycounter}%
  \fi
  Exercise \themycounter
}
\makeatother

\begin{document}

\begin{frame}[allowframebreaks]
\frametitle{\exercise}  % this seems expanded in each frame

  ABC

  \framebreak

  DEF
\end{frame}

\begin{frame}
\frametitle{\exercise}

GHI

\end{frame}

\end{document}

@gernot: Never say never with LaTeX :)

The basic idea is to test if the current page is the first page of a frame and only then to increase the counter.

\documentclass[t]{beamer}
\let\Tiny=\tiny
\newcounter{mycounter}
\setcounter{mycounter}{0}

\makeatletter
\def\exercise{%
    \ifnum\insertframestartpage=\thepage
        \refstepcounter{mycounter}
    \fi
    Exercise \arabic{mycounter}%
}
\makeatother

\begin{document}

\begin{frame}[allowframebreaks]
  \frametitle{\exercise}  % this seems expanded in each frame

  ABC

  \framebreak

  DEF
\end{frame}

\end{document}