Yes you are correct.
The problem is simple to fix, make it cost them CPU computation time.
Implement an SMTP Client <> SMTP Server cookie system, where by an adhoc association can be established between two systems, that the client can represent an arbitrary token to help build trust and reputation around it (or simply use IP address or SSL certificate hash).
Next define a mathematical problem that is cheap (in CPU cost) to setup and verify, but hard for the SMTP client to compute, forcing it to brute force the problem (this making the client pay the greater CPU cost). This needs to scale both linear and exponential.
Allow the server to define the problem to solve and the scale of the challenge, this more trusted clients have a cheap problem, brand new clients get hit with a harder CPU problem.
Built it all into the SMTP protocol.
Now the server is in complete control of the cost a particular client must pay to send the message, the client can decide to accept the cost or bounce the message.
Now sending from a ADSL link, from a foreign country or from a well known virtual host provider can all be scaled accordingly until the point SPAM becomes too expensive to rent enough server capacity.