Eu coloquei o seguinte em /etc/init.d/pwrstatd:
#!/bin/sh
### BEGIN INIT INFO
# Provides: pwrstatd
# Required-Start: udev
# Required-Stop:
# Should-Start:
# Default-Start: 2 3 4 5
# Default-Stop:
# Short-Description: PowerPanel to monitor CyberPower UPS
### END INIT INFO
Parecia fazer sentido confiar no udev.
Para verificar se isso funciona, se você tem o insserv e o graphviz instalados (esta questão é para o Debian depois de tudo), execute:
/usr/share/insserv/check-initd-order -g > boot.dot
dotty boot.dot