Ubuntu's Upstart parallellizes the startup sequence. There's a Getting-Started, a FAQ and a Wiki. Below two upstart jobs that form my first succesful try:

This is /etc/init/lwp-rename-host:

# lwp-rename-host - Rename the host if the DNS says it's not properly named
#
# Probe DNS and DHCP for the hostname of the system based on its IP number
# then alter the hostname accordingly
# This emits the signal lwp-rename-host on success

description     "Rename the host to DNS-/DHCP-provided name"

start on net-device-up

task

env DEFAULTFILE=/etc/default/lwp-rename-host

pre-start script
if [ -f "$DEFAULTFILE" ] ; then
        . ${DEFAULTFILE}
fi

end script

script
if ! [ "x$RENAME_HOST" = "xno" ] ; then
        if wai -f  ; then # 'wai' fixes the hostname if it can
                initctl emit lwp-host-renamed
                echo "# This line added automatically by lwp-rename-host upon success" >> ${DEFAULTFILE}
                echo "RENAME_HOST=no" >> ${DEFAULTFILE}
        fi
fi
end script
    

And this is /etc/init/lwp-fix-postfix-mailname.conf, which is started if init send the 'signal' lwp-host-renamed:

# lwp-fix-postfix-mailname - Fix the mailname when the system's hostname changes
#
# The mail config contains the system's name in several places
# This program changes them when the hostname changes
# 

description     "Fix the mailname when the hostname changes"

start on lwp-host-renamed

task

script

HOSTNAME=$(hostname)
FQDN=$(hostname --fqdn)
DOMAIN=$(hostname --domain)

echo ${FQDN} > /etc/mailname

postconf -e myorigin="/etc/mailname" myhostname="${HOSTNAME}" mydomain="${DOMAIN}" mydestination="localhost, localhost.${DOMAIN}, ${HOSTNAME}, ${FQDN}"

end script