Found the error message :

Error creating a DNS resolver socket: Permission non accordée at
/usr/lib/perl5/vendor_perl/5.8.7/Mail/SpamAssassin/DnsResolver.pm line 202.

(seems selinux problem, it says it is not allowed to create the socket)

probably selinux-related -> adding dwalsh in CCs

RE:
>  seems selinux problem, it says it is not allowed to create the socket
...
>  When I restart it later with security enforcing disabled it works

Yes, this sounds like an SELinux problem - reassigning to 
selinux-policy-targeted package.

I hope that when you say 'restart it later with security enforcing disabled'
that you did 'setenforce 0' or booted with 'enforcing=0', and did NOT disable
selinux entirely by booting with 'selinux=0' - otherwise you'll have to relabel.

I use setenforce. I'm trying very hard not to boot with 'selinux=0' or selinux
disabled via sysconfig, because I know the day I do it the easy way I'll never
go back

OK, well please try this to gather the information required to determine the
cause of this bug :

1. start out with an empty audit log -
   either empty it:
   #>/var/log/audit/audit.log
 or move it:
   # mv /var/log/audit/audit.log /var/log/audit/audit.log.bak

2. start spamassassin
   # service spamassassin start 2>&1 | tee /tmp/spastart.log

When the spamassassin start fails - is that what's happening here ? -
Please append the output of this command:
   # audit2allow </var/log/audit/audit.log | tee /tmp/spaudit.log
and gather the log files:
   # tar -cpf /tmp/spabug.tar /var/log/audit/audit.log  \
                              /tmp/spastart.log /tmp/spaudit.log
and attach the complete /tmp/spabug.tar file to this bug report.

Thank You!

I'll put the results inline since there is far too little to justify a tar

1. in spastart.log
Starting spamd:                                            [ÃCHOUÃ]

2. in maillog
spamd[4407]: Error creating a DNS resolver socket: Permission non accordée at
/usr/lib/perl5/vendor_perl/5.8.7/Mail/SpamAssassin/DnsResolver.pm line 202.

3. in spaudit.log
allow spamd_t port_t:udp_socket name_bind;
allow spamd_t user_home_t:dir { getattr search };

Stangely the result were not consistent. When started from the CLI the service
succeeded more often than it failed. On boot it's always failing

Fixed in selinux-policy-targeted-1.27.2-7

Unfortunately, rebooting with selinux-policy-targeted-1.27.2-7 shows the problem
still exist (no manual relabel is needed nowadays right ?)

audit2allow </var/log/audit/audit.log just after bootup shows theses spamd lines:

allow spamd_t devpts_t:chr_file ioctl;
allow spamd_t port_t:udp_socket name_bind;
allow spamd_t user_home_t:dir { add_name getattr remove_name search write };
allow spamd_t user_home_t:file append create getattr ioctl link read rename
setattr unlink write;

It's a bit more complex than when doing spamassassin tests on an already running
system

BTW looking at /var/log/audit/audit.log I see a lot of accesses to .spamassassin
and .pyzor blocked - I wonder if that's why pyzor has not been running well
there lately

Could you try selinux-policy-targeted-1.27.2-11 (Available in fedora-test)
or 
ftp://people.redhat.com/dwalsh/SELinux/FC4/
What port is it trying to bind to?

Will it work of with a rawhide system ?

For the port I haven't got hte faintest idea. I'm just reporting the error. But
the following snippet taken from the file referenced in the maillog error may be
enlightening:

  dbg("dns: name server: $ns, family: $family, ipv6: $ipv6");

  # find next available unprivileged port (1024 - 65535)
  # starting at a random value to spread out use of ports
  my $port_offset = int(rand(64511));  # 65535 - 1024
  for (my $i = 0; $i<64511; $i++) {
    my $lport = 1024 + (($port_offset + $i) % 64511);

    my %args = (
        PeerAddr => $ns,
        PeerPort => $self->{res}->{port},
        Proto => 'udp',
        LocalPort => $lport,
        Type => SOCK_DGRAM,
        Domain => $family,
    );

    if (HAS_SOCKET_INET6) {
      $sock = IO::Socket::INET6->new(%args);
    } else {
      $sock = IO::Socket::INET->new(%args);
    }
    $errno = $!;
    if (defined $sock) {  # ok, got it
      last;
    } elsif ($! == EADDRINUSE) {  # in use, let's try another source port
      dbg("dns: UDP port $lport already in use, trying another port");
    } else {
      # did we fail due to the attempted use of an IPv6 nameserver?
      $self->_ipv6_ns_warning()  if (!$ipv6 && $errno==EINVAL);
      die "Error creating a DNS resolver socket: $errno"; <-- Error that ends in
the logs
    }
  }
  defined $sock or die "Can't create a DNS resolver socket: $errno";

[root@rousalka tmp]# rpm -Uvh selinux-policy-targeted-1.27.1-2.11.noarch.rpm 
--force
attention: selinux-policy-targeted-1.27.1-2.11.noarch.rpm: Entête V3 DSA
signature: NOKEY, key ID 30c9ecf8
Préparation...              ########################################### [100%]
   1:selinux-policy-targeted########################################### [100%]
/usr/sbin/load_policy:  Warning!  Policy file argument
(/etc/selinux/targeted/policy/policy.20) is no longer supported, installed
policy is always loaded.  Continuing...
/sbin/restorecon reset /bin/su context
system_u:object_r:su_exec_t->system_u:object_r:bin_t
/sbin/restorecon reset /usr/bin/newrole context
system_u:object_r:newrole_exec_t->system_u:object_r:bin_t
/sbin/restorecon reset /usr/bin/spamc context
system_u:object_r:spamc_exec_t->system_u:object_r:bin_t
/var/lib is already defined in /etc/selinux/targeted/contexts/files/file_contexts,
/usr/sbin/genhomedircon will not create a new context.

Will reboot now

1. After reboot, no relabel is triggered, most services fail (including network)
2. -> reboot in non enforcing mode (which shows that spamassassin succeeds
without selinux BTW)
3. reinstall rawhide policy, reboot, autorelabel, reboot just to make sure, back
to square 1.

Sorry I thought you were on FC4.

Try selinux-policy-targeted-1.27.2-8.noarch.rpm

Available on ftp://people.redhat.com/dwalsh/SELinux/Fedora

This one works, thank you. I can't believe I've actually booted a system in
enforcing mode without any service failing :)

I'll go test squirrelmail now. I seem to remember it had selinux problems too

And this got broken a few days afterwards with the selinux policy 2 changes.
With selinux-policy-targeted-2.0.8-1 spamassassin can not create its dnsresolver
socket (it does not make the service fail on startup like before but it's a
serious problem still)

Dec  4 14:24:55 rousalka postfix/master[2356]: daemon started -- version 2.2.5,
configuration /etc/postfix
Dec  4 14:24:56 rousalka spamd[2363]: Error creating a DNS resolver socket:
Permission non accordée at
/usr/lib/perl5/vendor_perl/5.8.7/Mail/SpamAssassin/DnsResolver.pm line 202.


# audit2allow < /var/log/audit/audit.log | sort
allow cupsd_config_t cupsd_log_t:file { read write };
allow dovecot_auth_t dovecot_var_run_t:dir search;
allow dovecot_auth_t tmp_t:dir getattr;
allow dovecot_auth_t usr_t:lnk_file read;
allow dovecot_t etc_runtime_t:file read;
allow saslauthd_t self:capability setuid;
allow saslauthd_t tmp_t:dir getattr;
allow saslauthd_t usr_t:lnk_file read;
allow spamd_t port_t:udp_socket name_bind;
allow sysadm_su_t etc_runtime_t:file read;
allow sysadm_su_t tmp_t:dir getattr;
allow sysadm_su_t usr_t:lnk_file read;
allow system_chkpwd_t devpts_t:chr_file { read write };
allow system_dbusd_t self:process setcap;
allow updfstab_t tmpfs_t:dir getattr;

Well I was wrong - the resolver problem crashes spamassassin like before

New fixes for this in selinux-policy-targeted-2.1.4-1

Seems fixed again