# /etc/init.d/exim4 stop
Stopping MTA: exim4.
# pidof exim4
3559
# grep PIDFILE /etc/init.d/exim4 | sed 1q
PIDFILE="/var/run/exim4/exim.pid"
# ls -ld /var/run/exim4
ls: /var/run/exim4: No such file or directory
# mount | fgrep /var/run
varrun on /var/run type tmpfs (rw)

Well, that would explain it.

It turns out that the official Ubuntu exim4 package (which is in their core repository, not one of the less supported expanded ones) creates /var/run/exim4 in its post-install script. This probably works well on Debian, where I suspect that /var/run is part of a persistent filesystem, but works rather less well on Ubuntu (and fails mysteriously; 'exim4 stop' and 'exim4 restart' work fine after you install exim4 up until you reboot the machine). And Ubuntu clearly didn't make a systematic sweep through all packages looking for things that needed /var/run subdirectories when they decided to make /var/run a volatile filesystem.

(They weren't completely ignorant of the whole issue, since /etc/init.d/klogd carefully creates its /var/run directory every time.)

In general, I have not been pleased with Ubuntu's entire /etc/init.d setup. Coming from a Red Hat/Fedora Core environment, I keep finding things missing, like syslogging of the results or a consistent format for startup scripts and information about them. (Ubuntu has the start of this in some init scripts, with the 'BEGIN INIT INFO' section, but only about half of the init scripts on my test machine seem to use it.)

(I suspect that this anarchism and lack of features is a sign of Ubuntu's status as a relatively thin veneer over Debian. The Debian policy guide section on init.d scripts is pretty basic, which is a recipe for widely divergent init scripts.)