aptitude-r and softupdate

[Per Foreby]

I'm having problems with softupdate removing packages that were installed 
as recommends with aptitude-r. Example configuration

   aptitude-r
   ntp

This installs ntp-server and ntp-simple. (ntp-server is recommended by 
ntp, and depends on ntp-simple).

So far so good. However, on the first softupdate ntp-server and ntp-simple 
(and some 50 other packages) are removed. From the software log:

The following packages are unused and will be REMOVED:
   akode autogen ca-certificates dvd+rw-tools eject enscript esound-clients
   exuberant-ctags freepats fvwm-icons gdeb gimp-svg gnuhtml2latex jackd
   kdeprint libatk1.0-data libcompress-zlib-perl libfont-afm-perl libft-perl
   libgail-gnome-module libglib2.0-data libglib2.0-doc libhtml-format-perl
   libltdl3 libltdl3-dev libmail-sendmail-perl libmailtools-perl
   libmysqlclient14-dev libopts9 libopts9-dev libpango1.0-doc libpaper-utils
   libqt3-compat-headers librsvg2-bin libsamplerate0 libsasl2-modules
   libterm-size-perl libtimedate-perl libttf2 linuxdoc-tools lrzsz
   ntp-server ntp-simple orbit2 perl-suid perl-tk poster psfontmgr
   python2.3-iconvcodec sgmltools-lite texi2html wv x-ttcidfont-conf

Shouldn't aptitude be supposed to keep recommended packages until the 
package recommending them is gone? In the ntp example, the first package 
is still there and should prevent the other packages from being removed:

   Desired=Unknown/Install/Remove/Purge/Hold
   | Status=Not/Installed/Config-files/Unpacked/Failed-config/Half-installed
   |/ Err?=(none)/Hold/Reinst-required/X=both-problems (Status,Err: uppercase=bad)
   ||/ Name           Version        Description
   +++-==============-==============-============================================
   ii  ntp            4.2.0a+stable- Network Time Protocol: network utilities
   rc  ntp-server     4.2.0a+stable- Network Time Protocol: common server tools
   rc  ntp-simple     4.2.0a+stable- Network Time Protocol: daemon for simple sys

Another thing: If I run aptitude manually on a newly installed computer
(before the first softupdate), it reports no errors, and doesn't attempt 
to remove anything.

The workaround (which I suppose must work) is to explicitly list all of 
these packages, but it shouldn't be necessary. So what am I doing wrong? 
Or is this maybe a bug in fai?

The versions I'm using are:
   server (sarge): fai-server 2.10.1
   client (sarge): fai-client 2.10.5

/Per