According to reports from Australia, Telstra secured hefty discounts from Microsoft in return for rolling out Windows XP, Office 2003, Exchange 2003 and other Microsoft software products to 40,000 desktops.
The value of the four-year deal is thought to be in the region of £8m.
By deciding to buy Microsoft's software, Telstra appears to be executing something of a U-turn. Last year it announced it would deploy Sun's Java Desktop, as part of a push to cut its annual IT spending in half. Sun was not immediately able to comment on the issue on Monday, and it is not clear whether the deal with Microsoft means that the Java Desktop is no longer being deployed.
Microsoft Australia managing director Steve Vamos has been quoted in the Australian media criticising the "philosophical discussion" about "open source versus commercial software alternatives" that he said has been taking place.
"Open source, commercial software and all technology is ultimately judged by fit for purpose and value for money judgments made by customers. Open-source-developed products are increasingly managed within the realm of commercial industry players like IBM, Novell and Red Hat," Vamos was quoted as saying by the Australian.
In the UK, the practice of pushing Microsoft for lower licensing costs by threatening to go with Linux instead is becoming known as 'doing a Newham', after the London borough council that took part in an open-source desktop trial before eventually sticking with Microsoft.
Microsoft has been citing this case as an example of how its software can offer greater productivity than an open-source alternative. But some familiar with the Newham case have claimed that Microsoft had to make dramatic reductions in its prices in order to avoid a high-profile defection to Linux.
Nick Barley, director of marketing at Microsoft, said back in June that more companies are using the threat of Linux when negotiating deals with Microsoft.