It looks like when disabling a service on Debian, Puppet deletes all the /etc/rc?.d links. This isn't the correct way to disable a service since it mimics the service not being installed at all. The next time the package is updated, the service will be linked back in and dpkg will attempt to start it.
The correct way to disable a service is to rename the S* links to K* links but otherwise leave them in place. If done this way, the service will not be started even on upgrades.
update-rc.d could be used to set the links up that way, but it may be easier just to manipulate the file system since you have to look at the file system to figure out what priority to use for the stop links anyway, at least currently. (This will all change eventually with dependency-managed boots, which are coming hopefully for lenny.)