The local.cf file is the same on both.
There are no user_prefs files getting in the way that are altering the behavior of the add_header (that I can see).
Where else should I look?
How is spamassassin called? Is it the same on both, or does the one that's not working use a tool like Amavis or MailScanner which does it's own header generation?
