Often, openVZ VPSes that are left behind by their providers are stuck with old kernel versions.
For this occasion, my VPS had 2.6.32-042stab127.2 and after an upgrade, the server’s sshd service wouldn’t start on boot.
Digging on the problem, I found out that on 2.6.32-042stab134.7 it was fixed.
To temporarily bypass the problem you can create the directory /var/run/sshd yourself and start the service manually:
# mkdir -p /var/run/sshd # service sshd start
That will bring the sshd back up.
For a permanent fix, you’ll have to edit /usr/lib/tmpfiles.d/sshd.conf with:
d /run/sshd 0755 root root
Then reboot and you’ll see that the service starts without problems.