Funnily enough, the server doesn't seem to stop for me, even though it returns "service stopped"; ssh localhost still lets me in.
ps -ef | grep sshd <kill all the processeses> /etc/init.d/sshd start /etc/init.d/sshd stop ps -ef | grep sshd