The reason that Microsoft is winning this war is because they've got lots of patience and lots of resources. They can afford to send dozens of people to meet with ministers. In Australia they have millions of dollars for an 'educational fund' which is really for undercutting any open source deployment bid.
Where we can combat them is by not doing drop-ship, set-and-forget deployments. They have to get long-term support. We have to build enthusiasm and dedication in the people working with Linux in the deployment so they can see the reason why it's good. We have to prepare them (just as any lobbyist does) to combat the FUD from Microsoft, to point out the flaws in their arguments, and to provide expert assistance and legal counsel when Microsoft inevitably makes its move.
I suspect there's a culture in FOSS companies of 'why should we be the ones to take on Microsoft'. We already have organisations like the FSF, the SFLC, the EFF and others who have the access and the credibility at the business level to do the work of countering MS FUD. We need to support those organisations and build them. Otherwise we will keep ceding ground, we will keep seeing these deployments reinstalled with Windows, because we expect to just do our work and move on and Microsoft is much more patient an adversary than that.