Eu finalmente descobri eu mesmo. Os recentes scripts init da Debian apresentam alguns comentários especiais no início dos arquivos. Pode ser especificado, que tipo de serviços eles fornecem e quais devem estar disponíveis primeiro. É descrito aqui muito bem:
Então, no meu caso especial, tive que editar /etc/inti.d/dnsmasq
e adicionar openvpn
aos requisitos:
# Required-Start: $network $remote_fs $syslog openvpn