The article notes that since the virus was added to the list of malware removed by Microsoft's Malicious Software Removal Tool, the numbers of computers infected by it have shrunk significantly. This suggests that the computers will are still infected are those which are not choosing to apply security updates.
Regardless of whether Microsoft would be "within its rights" to start something like this, it would still be liable for any damage caused to computers which became broken by the cleaning (see the next to last paragraph of the article).
We would need some way to verify that our computers were "clean." Without this certificate (or whatever), we wouldn't be allowed access to web pages or http ports. But we would be free to get the cert from any vendor we could.
Even with this method, there is a vulnerability to spoofing the certificate.