By far the most important thing that a service provider can do to reduce spam is to ensure that any mail servers in operation accept only outgoing mail from machines within their own domains. This prohibits SMTP relaying, denying spammers a necessary component of anonymity. By this definition, anyone operating an Internet connected MTA is a service provider. If you operate an Internet-connected MTA, ensure that SMTP relaying is not enabled. This is especially important since most MTA software still ships with SMTP relaying turned on by default.
With SMTP relaying disabled, your MTA can verify that attempts to send mail are coming from inside your own domain. It can do so by examining IP addresses in incoming packets and performing a reverse domain name service (DNS) lookup on them. Any connections from outside listed domains are refused service. You can verify this with any large ISP: telnet to port 25 on a mail server at a large ISP, and note the message that is shown when you try to send mail.
Some administrators feel that they need to use SMTP relaying to meet their business requirements. For example, suppose that a large company had many traveling salespeople who wished to send and receive email from the company mail server. The travelers may reasonably expect to be able to send mail via the company mail server, even though their ISP issues a new IP address each time they connect. The temptation to enable relaying in this situation is extreme. In reality, it is probably ...