There are plenty of rules that could be set up to prevent rogue systems from sending spam, but the problem is with getting network operators and individual server administrators on board. Trying to get all network operators (or ISPs) around the world doing something is like herding cats. Trying to get all individual server administrators to do something is like herding millions of catnip-infused cats.
Your thought about MX records is not quite right. There is a difference between servers that recieve mail (which should be pointed to by MX records) and servers that send mail (which should have valid PTR records in reverse DNS for their IP). While a single server may perform both duties, that is not by any means guaranteed. One action that would block a large number of infected systems from delivering their spam would be receiving mail servers blocking all mail from senders that do not have a valid RDNS record. This is the correct version of your proposal, and some major providers already do this. An even greater benefit could be achieved if all ISPs were to block outbound traffic headed for TCP port 25 by default, requiring subscribers to "opt-in" to initiate port 25 traffic. Some ISPs already do this, but far too many do not. Yet another good measure would be for recipients to block mail from servers that fail to identify themselves with a valid fully-qualified domain name in their HELO message and require that domain to resolve by DNS. Like the RDNS solution, this would require all legitimate mail server operators to set their sending servers up properly. As more receiving operators start blocking non-compliant mail servers, we may slowly push more sending server operators to do things right, but it is a long, slow process when users demand that every legitimate message get through.