Replace the init script provided by the package with this one:

<code>
#! /bin/sh
#
# postgrey      start/stop the postgrey greylisting deamon for postfix
#               (priority should be smaller than that of postfix)
#
# Author:       (c)2004-2006 Adrian von Bidder <avbidder@fortytwo.ch>
#               Based on Debian sarge's 'skeleton' example
#               Distribute and/or modify at will.
#
# Version:      $Id: postgrey.init 1436 2006-12-07 07:15:03Z avbidder $
#
### BEGIN INIT INFO
# Provides:          postgrey
# Required-Start:    $syslog $local_fs $remote_fs
# Required-Stop:     $syslog $local_fs $remote_fs
# Default-Start:     2 3 4 5
# Default-Stop:      0 1 6
# Short-Description: Start/stop the postgrey daemon
### END INIT INFO

set -e

PATH=/sbin:/bin:/usr/sbin:/usr/bin
DAEMON=/usr/sbin/postgrey
DAEMON_NAME=postgrey
DESC="postfix greylisting daemon"
DAEMON_USER=postgrey

PIDFILE=/var/run/$DAEMON_NAME.pid
SCRIPTNAME=/etc/init.d/$DAEMON_NAME

# Gracefully exit if the package has been removed.
test -x $DAEMON || exit 0

. /lib/lsb/init-functions

# Read config file if it is present.
if [ -r /etc/default/$DAEMON_NAME ]
then
    . /etc/default/$DAEMON_NAME
fi

POSTGREY_OPTS="--pidfile=$PIDFILE --daemonize $POSTGREY_OPTS"
if [ -z "$POSTGREY_TEXT" ]; then
    POSTGREY_TEXT_OPT=""
else
    POSTGREY_TEXT_OPT="--greylist-text=$POSTGREY_TEXT"
fi

ret=0

do_start()
{
        # Return
        #   0 if daemon has been started
        #   1 if daemon was already running
        #   2 if daemon could not be started
        start-stop-daemon --start --quiet --pidfile $PIDFILE --exec $DAEMON --test > /dev/null \
                || return 1
        start-stop-daemon --start --quiet --pidfile $PIDFILE --exec $DAEMON -- \
                $POSTGREY_OPTS "$POSTGREY_TEXT_OPT" \
                || return 2
}

do_stop()
{
	# Return
	#   0 if daemon has been stopped
	#   1 if daemon was already stopped
	#   2 if daemon could not be stopped
	#   other if a failure occurred
        start-stop-daemon --user $DAEMON_USER --stop --quiet --retry=TERM/30/KILL/5 --pidfile $PIDFILE
        RETVAL="$?"
        [ "$RETVAL" = 2 ] && return 2

	# Wait for children to finish too if this is a daemon that forks
	# and if the daemon is only ever run from this initscript.
	# If the above conditions are not satisfied then add some other code
	# that waits for the process to drop all resources that could be
	# needed by services started subsequently.  A last resort is to
	# sleep for some time.
	start-stop-daemon --user $DAEMON_USER --stop --quiet --oknodo --retry=0/30/KILL/5 --exec $DAEMON
	[ "$?" = 2 ] && return 2
	# Many daemons don't delete their pidfiles when they exit.
	rm -f $PIDFILE
	return "$RETVAL"

}

do_reload()
{
	#
	# If the daemon can reload its configuration without
	# restarting (for example, when it is sent a SIGHUP),
	# then implement that here.
	#
	start-stop-daemon --stop --signal 1 --quiet --pidfile $PIDFILE
	return 0
}

case "$1" in
  start)
	[ "$VERBOSE" != no ] && log_daemon_msg "Starting $DESC" "$DAEMON_NAME"
        do_start
	case "$?" in
		0|1) [ "$VERBOSE" != no ] && log_end_msg 0 ;;
		2) [ "$VERBOSE" != no ] && log_end_msg 1 ;;
	esac
        ;;
  stop)
	[ "$VERBOSE" != no ] && log_daemon_msg "Stopping $DESC" "$DAEMON_NAME"
        do_stop
	case "$?" in
		0|1) [ "$VERBOSE" != no ] && log_end_msg 0 ;;
		2) [ "$VERBOSE" != no ] && log_end_msg 1 ;;
	esac
        ;;
  reload|force-reload)
	[ "$VERBOSE" != no ] && log_daemon_msg "Reloading $DESC" "$DAEMON_NAME"
        do_reload
	case "$?" in
		0|1) [ "$VERBOSE" != no ] && log_end_msg 0 ;;
		2) [ "$VERBOSE" != no ] && log_end_msg 1 ;;
	esac
        ;;
  restart)
        do_stop
        do_start
        ;;
  status)
        status_of_proc -p $PIDFILE $DAEMON "$DAEMON_NAME" 2>/dev/null
        ret=$?
        ;;

  *)
        echo "Usage: $SCRIPTNAME {start|stop|restart|reload|force-reload|status}" >&2
        exit 1
        ;;
esac

exit $ret
</code>

Source: http://sources.debian.net/src/postgrey/1.35-1/debian/postgrey.init/