How do I get the right number of pauses after a list in beamer?

Without the \pause command, "On the first or third slide" has no specification for when to appear, which means it always appears. With the \pause command, it uncovers the list items one at a time until they are all uncovered, and then pauses again, which is why you have the repeat slide (since nothing changes between uncovering the last item and pausing).

The solution is to specify when you want the items after the list to appear. One method of accomplishing this is to surround it with an \uncover command:

\documentclass{beamer}
\begin{document}
\begin{frame}
\begin{itemize}[<+->]
\item On the first slide
\end{itemize}
\uncover<+->{
On the second slide
}
\end{frame}
\end{document}

Edit

In response to your edit, here's another way to solve your problem. You are using \pause in combination with the list option [<+->], which adds its own pauses and so results in double pauses sometimes. If you really prefer to not give up \pause, then you can fix your example's behaviour by using it exclusively:

\documentclass{beamer}
\begin{document}
\begin{frame}
On the first slide
\pause
\begin{itemize}
  \item On the second slide.
    \pause On the third slide
  \pause\item On the fourth slide
\end{itemize}
\end{frame}
\end{document}

This also works in your first example:

\documentclass{beamer}
\begin{document}
\begin{frame}
\begin{itemize}
  \item On the first slide
  \pause\item On the second slide
\end{itemize}
\pause On the third slide
\end{frame}
\end{document}

The potential down side of this approach is that \pause stops everything after it on the current frame from appearing until the pause has passed, even if you specify that it should appear earlier. For example,

\documentclass{beamer}
\begin{document}
    \begin{frame}
        Here are important points:
        \begin{itemize}
            \item Point on Slide 1
            \pause\item Point on Slide 2
            \pause\item Point on Slide 3
        \end{itemize}
        \uncover<1-3>{
            I want to emphasize this on every slide:\\ Always remember these points!\\ (But it only appears on the third slide)
        }
    \end{frame}
\end{document}

On the other hand, with less code you can achieve this effect simply:

\documentclass{beamer}
\begin{document}
\begin{frame}
Here are important points:
\begin{itemize}[<+->]
  \item Point on Slide 1
  \item Point on Slide 2
  \item Point on Slide 3
\end{itemize}
Always remember these points!
\end{frame}
\end{document}

The solution I ended up with was to define two refinements of the \pause command, one for inside a list and one for just after, which made the pauses work as I expected them to. They adjust beamerpauses accordingly.

The definitions are:

% For after a list
\newcommand{\itpause}{%
\addtocounter{beamerpauses}{-1}%
\pause
}

% For within a list
\newcommand{\iitpause}{%
\addtocounter{beamerpauses}{-1}%
\pause
\addtocounter{beamerpauses}{1}%
}

Use as:

\documentclass{beamer}
%\url{https://tex.stackexchange.com/q/682/86}
% For after a list
\newcommand{\itpause}{%
\addtocounter{beamerpauses}{-1}%
\pause
}

% For within a list
\newcommand{\iitpause}{%
\addtocounter{beamerpauses}{-1}%
\pause
\addtocounter{beamerpauses}{1}%
}

\begin{document}
\begin{frame}
\begin{itemize}[<+->]
\item First slide
\iitpause Second slide
\item Third slide
\end{itemize}
\itpause
Fourth slide
\end{frame}
\end{document}