I have configured ssh-server to be not running by default (no symlink
in rc*.d directories to /etc/init.d/ssh), since I start the sshd only
rarely and only when I'm on "secure" network. And even though ssh was
not running, upgrading ssh via apt-get "restarted" the server,
effectively starting it:

Setting up openssh-server (1:5.2p1-2) ...
update-rc.d: warning: ssh start runlevel arguments (2 3 4 5) do not
match LSB Default-Start values (none)
update-rc.d: warning: ssh stop runlevel arguments (none) do not match
LSB Default-Stop values (1)
Restarting OpenBSD Secure Shell server: sshd.

I think the sshd should only be restarted when it is actually running,
otherwise it can open up to password-guessing attacks or alike on some
configurations when I do not expect sshd to be automatically running
in first place...

The defined way to do this in the sysv-rc scheme is to add 'K' links to
each of the rc*.d directories, rather than just deleting the links
altogether.  If you delete the links, then the state is undefined and
you may well find that packages sometimes put 'S' links back.  I suspect
that's what's happened in this case.

(Yes, this is weird and confusing; but it's a property of how sysv-rc is
defined rather than really being the fault of the openssh packaging ...)