I am also seeing this at one of my sites, from a clean install + the update script (including the spam and Clam contribs from jesper).
I am tried every combination of rbl and no rbl, spam filter on and off, and the only situation where it works is if I turn off scanning outgoing email in the anti virus panel.
I have other sites where this works fine...