SMTP returning outbound mail

I recently corrected an mis configured Exchange 2000 server, stopping it from relaying. Most outbound SMTP mail seems to go out with out difficulty, however mail to some addresses is returned by “System Admin” stating youdon’t have permission… I configured Exchange to allow all computers who authenticate to relay and I still get mail returned. As far as I know our server is no longer “black-listed”. These are addresses that we regularly correspond with and I need to get the connections backup.