Not every server needs to understand it. Only the ones wanting to participate. If you choose to filter by PoW and a server does not provide PoW, you will still receive all of its emails just flagged as spam. So email PoW roll out can work iteratively.
True, but then a spammer need only implement PoW in their malware framework. Most spam today comes from malware infected PC's and rented VM's. CPU and network resources are free. The biggest challenge for the spammer will be getting updated malware deployed to support PoW, assuming their existing malware can't update itself via a command and control server. Unless you are selling crypto keys that are used in this PoW that can be revoked when abused, the malware need only know how to solve the puzzle.
If they add PoW to their malware, it will slow them down or even alert users / admins because of the high CPU usage it will cause.
If all the spam came from a tiny set of hosts this would for sure be true. This for sure used to be the case. These days spam comes from millions of infected PC's and VM's. You will almost never see more than a few dozen connections come from the same host in a day, with exception to rented VM's because they have more resources. Spammers can control how much is sent from which classes of infected hosts. This also applies to the logic in their malware for things like brute forcing ssh/https/mysql connections. The victim rarely notice the malware any more, as it runs at lower CPU priority. Some of the malware is even polite enough to use a single core. Even telling ISP's and VPS providers a host is infected can take weeks or months to get someone to look into it.