Sometimes Outlook safesender list is not updated. Please check that text file is accessible from the client machine.
If still a problem there is replace for the safesender file with Outlook safe sender text file (export from Outlook and replace in sysvol).
Check the permission of that text file (authenticated users should have read & execute and read permission).

We have deployed on Outlook 2003 and 2007 as well. You have to add four adm templates for that. Two for 2003 and two for 2007.

See the below links for additional help.

ADM Templates Name list:

adm template name:outlk11-junkemailtrigger.adm
adm template name:Outlk11.adm
adm template name:outlk12-junkemailtrigger.adm
adm template name:Outlk12.adm