Xandros has created a Linux distribution based on Debian for both desktops and servers. It also sells Scalix open-source mail servers, having acquired the company in July.
The pact is one of a series of agreements between the software giant and Linux companies, all aimed at bolstering interoperability between Microsoft's proprietary software and open-source alternatives.
Xandros' deal with Microsoft, which was signed in June, originally focused on improving interoperability between their servers to make it easier for IT professionals to manage both sets of systems.
On Wednesday, the two companies said they would extend that deal to help customers deploy Windows-based wireless e-mail offerings using Scalix servers.
Xandros will develop a server-side implementation of Exchange ActiveSync to enable wireless synchronization without having to install third-party software.
Windows Mobile-based e-mail has become increasingly popular as Microsoft tries to tap into a lucrative marketplace in which BlackBerry maker Research in Motion is a commanding presence.
"With the ubiquity of Windows Mobile-based smart phones, this agreement will enable us to provide the same range of Scalix connectivity choices for users of desktop, laptop and handheld devices that they currently enjoy with Microsoft Exchange," said Xandros' chief executive, Andreas Typaldos.
The two protocols that Xandros will license are Exchange ActiveSync and the Outlook-Exchange Transport Protocol. Xandros says it will release the first results from its use of the protocols in six to 12 months.
As part of its agreements with Linux vendors, Microsoft has said that it won't sue customers of those companies.
For users of other open-source vendors--the largest of which is Red Hat--Microsoft says it will not sue for now.
Richard Thurston of ZDNet UK reported from London.