Well, the problem was the template out of which I created my VPS. I don't know why, the line to start klogd in /etc/init.d/syslog was commented out. Started klogd, logs are happily showing in /var/log/messages