HELP! server used for relay but relaying denied

Our server has been used by s spammer, fir the second time (also some weeks ago.I already had the necessary settings is the server config document. When I telnet to the server on port 25 and try to send from from an external domain to an external domain I get the message: relying denied in your configuration.

I also had set "Verify sender’s domain in DNS:"to enabled.

I wonder and was surprised that mail was relayed while settings seems oke.

Please help.