그런 증세를 직접 경험해 본적은 없지만..
centos 7.2 까지 버전에서 systemd 버그가 있습니다.
서버 종료시 데몬 종료 과정에서 멈추는 증세와..시작 단계에서 문제가 발생할수도 있어보입니다.

콘솔로 로그인 하신 후 systemctl status sshd 로 어느 단계에서 failed 되는지 확인해 보시는게 좋을듯 합니다.