So what we got here. A lot of spam and error message in mail.log:

May 12 07:02:04 venus spamd[6392]: spamd: connection from localhost [127.0.0.1]:38665 to port 783, fd 5
May 12 07:02:04 venus spamd[6392]: spamd: checking message <l337@example.com> for qscand:1019
May 12 07:02:04 venus spamd[6392]: plugin: eval failed: available_nameservers: No DNS servers available!
May 12 07:02:04 venus spamd[6392]: spf: lookup failed: available_nameservers: No DNS servers available!

Turns out spamd was not doing fully its job due to DNS failures. DNS was well configured and connection to the internet available.
There is a bug in Net::DNS and the solution was provided on SpamAssassin's bug tracker page: https://bz.apache.org/SpamAssassin/show_bug.cgi?id=7057 .

Steps followed

Backed up the current DnsResolver.pm:

venus:~# cp /usr/local/share/perl/5.10.0/Mail/SpamAssassin/DnsResolver.pm /usr/local/share/perl/5.10.0/Mail/SpamAssassin/DnsResolver.pm.

Saved the patch lines found in the solution page in a file:
NOTE: "-" means that line will be removed from file and "+" means that line will be added.

venus:~# cat dns_resolver.patch
--- spamassassin/trunk/lib/Mail/SpamAssassin/DnsResolver.pm	2014/06/18 16:47:04	1603517
+++ spamassassin/trunk/lib/Mail/SpamAssassin/DnsResolver.pm	2014/06/18 16:48:04	1603518
@@ -204,8 +204,10 @@
     @ns_addr_port = @{$self->{conf}->{dns_servers}};
     dbg("dns: servers set by config to: %s", join(', ',@ns_addr_port));
   } elsif ($res) {  # default as provided by Net::DNS, e.g. /etc/resolv.conf
-    @ns_addr_port = map(untaint_var("[$_]:" . $res->{port}),
-                        @{$res->{nameservers}});
+    my @ns = $res->UNIVERSAL::can('nameservers') ? $res->nameservers
+                                                 : @{$res->{nameservers}};
+    my $port = $res->UNIVERSAL::can('port') ? $res->port : $res->{port};
+    @ns_addr_port = map(untaint_var("[$_]:" . $port), @ns);
     dbg("dns: servers obtained from Net::DNS : %s", join(', ',@ns_addr_port));
   }
   return @ns_addr_port;

Patched DnsResolver.pm:

venus:~# patch -p0 < dns_resolver.patch
can't find file to patch at input line 3
Perhaps you used the wrong -p or --strip option?
The text leading up to this was:
--------------------------
|--- spamassassin/trunk/lib/Mail/SpamAssassin/DnsResolver.pm	2014/06/18 16:47:04	1603517
|+++ spamassassin/trunk/lib/Mail/SpamAssassin/DnsResolver.pm	2014/06/18 16:48:04	1603518
--------------------------
File to patch: /usr/local/share/perl/5.10.0/Mail/SpamAssassin/DnsResolver.pm
patching file /usr/local/share/perl/5.10.0/Mail/SpamAssassin/DnsResolver.pm

Spamassassin restarted:

venus:~# /etc/init.d/spamd restart
Restarting SpamAssassin Mail Filter Daemon: spamd.

Now, error is gone and most important: no more spam again!