Looks like startup script is a bit incorrect.
Try to do following changes:
in stop section add "--retry 60" to start-stop-daemon:
stop)
log_daemon_msg "Stopping NetXMS server" "netxmsd"
start-stop-daemon --stop --quiet --pidfile $PIDFILE --retry 60
log_end_msg $?
Add following section into /etc/init.d/netxmsd (just after #!/bin/sh):
### BEGIN INIT INFO
# Provides: netxmsd
# Required-Start: $remote_fs network nxagentd mysql
# Required-Stop: $remote_fs mysql
# Default-Start: 2 3 4 5
# Default-Stop: 0 1 6
# Short-Description: NetXMS server initscript
# Description: NetXMS server startup script
### END INIT INFO
After change is made - run "update-rc.d netxmsd defaults"
