Microsoft has San Francisco, Minnesota, the United States Department of Agriculture, the European Environmental Agency, and the Regional Government of Catalonia.

But Google is doing pretty well too, with Los Angeles, Orlando, Singapore’s ministry of education, four states in Mexico, and the U.S. National Oceanic and Atmospheric Administration.

Those government agencies represent some of the trophy customers for Microsoft and Google as the two rivals wrestle for converts to their competing versions of cloud computing.

The public sector has historically been one of the biggest buyers of computer gear and services; in the United States, the government’s total annual IT budget is $75 billion. As local, state, and federal agencies follow the private sector in embracing cloud computing, Microsoft and Google want to grab as much of that business as they can.

Each company has a fleet of salespeople calling on government accounts, and each is eager to give the impression that momentum is on its side. Every significant marketplace victory is thus trumpeted with press releases and other fanfare. Some competitions for customers end up in court, as when Google sued the U.S. Department of the Interior in hopes of undoing a $59.3 million deal it made with Microsoft; the issue is still pending.

Government organizations currently use cloud technology mostly for e-mail. In the past, that function has typically been handled on servers running inside an agency’s own facilities; the software was usually either Lotus Notes or Microsoft Exchange, one of the cornerstones of Microsoft’s business-software franchise. But earlier versions of Exchange e-mail have been unpopular with users in government and the private sector alike, who have complained about its glacial speeds and frustratingly small in-box limits.

Google, sensing an opening, began marketing a special version of its popular Gmail service tailored for government agencies. One change: data is kept in its own bank of computers, separate from those used for “civilian” Gmail.

In 2009, the city of Los Angeles chose Gmail for its 30,000 employees. That decision was a watershed. Jon Walton, chief information officer for San Francisco, says that governments had previously been reluctant to consider e-mail outsourcing for security reasons. “But L.A. broke that taboo,” he says. “I give all the credit to L.A. for opening up this opportunity for everyone.”

The L.A. announcement was one of several jolts Microsoft received before it beefed up its cloud service. Now Microsoft will run a government agency’s Exchange servers in the company’s own data centers, which eliminates the need for hardware on the user’s premises.

One of Microsoft’s key advantages, says Susie Adams, chief technology officer at Microsoft Federal, is that most employees who work at computers, both in and out of government, are longtime users of Microsoft’s Office products and don’t wish to switch to something unfamiliar.

Google counters that its cloud-based offerings, like Gmail and Google Docs, are both less expensive and less of a hassle to run. David Mihalchik, head of Google Apps Federal, says most of the company’s success to date has been with Gmail and other collaboration products. No big government agency has yet to dump all its Office software for Google products, he says, though some are beginning to flirt with the idea.

So who is ahead? Shawn P. McCarthy, IDC’s director of research involving the government sector, says that Google had an early lead, but Microsoft has since caught up. The contest is in its very early days, however.

Both companies stress that cloud-based e-mail is ideal for the current fiscal environment, in which government at all levels is starved for revenue. While both sides say their cloud services save money, McCarthy says it’s hard to know just how much: the terms of big government contracts are usually kept secret, lest future customers become aware of the sorts of discounts they might be able to negotiate.

The two companies, after all, are eager to deal.