The problem is that theorems are lists and lists introduce break points at their beginning and ending; as you put proofs inside theorems, your theorem ending has two break points (so preventing the break needs to overcome both).
The simplest would probably be to rewrite the theorem environments without using lists, but that means loosing (or rewritting) support of ntheorem features. And it's not guaranteed it will always work as things like \[...\] may also introduce break points (but setting \postdisplaypenalty=10000 inside the theorem does the trick).
Here's an attempt; I have tried to eliminated all possible break points, but using things like {center}, {enumerate}, {itemize} might introduce a break point (with the enumitem package you can use the endpenalty=10000 key to prevent this). This implementation supposes that your proofs will always end just before \end{theorem}.
\documentclass{memoir}
\usepackage{amsmath}
\usepackage{lipsum}
\usepackage{multido,xcolor}
\newcounter{theorem}[chapter]
\newenvironment{theorem}
{\par\noindent\theoremhang\par\nobreak\noindent
\refstepcounter{theorem}\postdisplaypenalty=10000 %
{\sffamily\bfseries\upshape Theorem \thetheorem}\ \ignorespaces}
{\par\nobreak\noindent\theoremhung\par\addvspace{\topsep}}
\newenvironment{proof}
{\par\addvspace{\topsep}\noindent{\sffamily\bfseries\upshape Proof}\ \ignorespaces}
{\par\nobreak}% no spacing here so that supposes you will always use {proof} inside {theorem} or else there might be some problems.
\newcommand{\theoremhang}{% top theorem decoration
\begingroup%
\setlength{\unitlength}{.005\linewidth}% \linewidth/200
\begin{picture}(0,0)(1.5,0)%
\linethickness{0.45pt} \color{black!50}%
\put(-3,2){\line(1,0){206}}% Top line
\multido{\iA=2+-1,\iB=50+-10}{5}{% Top hangs
\color{black!\iB}%
\put(-3,\iA){\line(0,-1){1}}% Top left hang
\put(203,\iA){\line(0,-1){1}}% Top right hang
}%
\end{picture}%
\endgroup%
}%
\newcommand{\theoremhung}{% bottom theorem decoration
\begingroup%
\setlength{\unitlength}{.005\linewidth}% \linewidth/200
\begin{picture}(0,0)(1.5,0)%
\linethickness{0.45pt} \color{black!50}%
\put(-3,0){\line(1,0){206}}% Bottom line
\multido{\iA=0+1,\iB=50+-10}{5}{% Bottom hangs
\color{black!\iB}%
\put(-3,\iA){\line(0,1){1}}% Bottom left hang
\put(203,\iA){\line(0,1){1}}% Bottom right hang
}%
\end{picture}%
\endgroup%
}%
\begin{document}
\chapter{First chapter}
\lipsum[1]
\begin{theorem}%
If~$G$ is a connected graph of order $n\geq 3$ and size~$m$, then
\[
g(G)\geq \frac{m}{6}-\frac{n}{2}+1.%
\]
\begin{proof}%
Suppose a connected graph~$G$ of order $n\geq 3$ and size~$m$ is embedded in a surface of genus~$g(G)$, thus producing~$f$ faces. Then it follows by Theorem~XX that every face is a 2-cell and hence by Theorem~YY that $n-m+f=2-2\,g(G)$. An identical argument as in the proof of Theorem~ZZ shows that $3f\leq 2m$ and so
\[
2-2\,g(G)=n-m+f\leq n-m+\frac{2m}{3},%
\]
from which the desired inequality follows.%
\end{proof}%
\end{theorem}%
\lipsum[2]
\begin{theorem}%
If~$G$ is a connected graph of order $n\geq 3$ and size~$m$, then
\[
g(G)\geq \frac{m}{6}-\frac{n}{2}+1.%
\]
\end{theorem}%
\lipsum[3]
\begin{theorem}%
\lipsum[4]
\end{theorem}%
\lipsum[5]
\end{document}
As tohecz mentions in his comment, the difference in the styles that you mention is the one of the amsthm package: however, the amsbook class internally defines the remark and definition styles in a different way. Here are the definitions:
\def\th@definition{%
\let\thm@indent\indent
\thm@headfont{\scshape}% heading font small caps
\let\thmhead\thmhead@plain \let\swappedhead\swappedhead@plain
\thm@preskip.5\baselineskip\@plus.2\baselineskip
\@minus.2\baselineskip
\thm@postskip\thm@preskip
\upshape
}
\def\th@remark{%
\let\thm@indent\indent
\thm@headfont{\scshape}% heading font small caps
\let\thmhead\thmhead@plain \let\swappedhead\swappedhead@plain
\thm@preskip.5\baselineskip\@plus.2\baselineskip
\@minus.2\baselineskip
\thm@postskip\thm@preskip
\upshape
}
As you can see, both styles behave exactly the same when using amsbook.cls.
Best Answer
Here's a solution with
thmtools, which eases defining new theorem styles: