Judging by market share only, Google's Google Apps Web-based e-mail and collaboration suite hasn't begun to loosen Microsoft Office's tight rein on the corporate world.But mindshare is a different story. Google has been ramping up buzz through an aggressive ad campaign and PR efforts to parade a steady stream of customers that have "gone Google".The search giant recently announced that 3 million businesses now use Google Apps.Last week, Google had a high-profile enterprise win with Virgin America Airlines, which decided to move from Microsoft Exchange to Google Apps. But the bulk of Google Apps most notable migrations are within the public sector \u2014 and now a battle for cash-strapped state government agencies is underway between Google Apps and Microsoft's BPOS (business productivity online suite) cloud service for e-mail and collaboration apps (recently rebranded as Office 365).With tighter budgets than most corporate entities, government agencies have been more apt to move to cloud-based services that allow e-mail and documents to be stored in remote data centers.Google Blindsides Microsoft in LA, then FaltersA year ago, Google pulled the rug out from under Microsoft when it won out in a competitive process to migrate the City of Los Angeles' e-mail system from Novell's Groupwise platform to Google Apps. Yet that migration has been problematic for Google. It missed a June 30 deadline to have all city employees moved to Google Apps and has struggled to meet the LAPD's strict security guidelines.As of now, Google is not saying definitively when the City of LA migration will be finished, but the company maintains that the Google Apps migration will ultimately save Los Angeles taxpayers $5.5 million in cost savings.City of LA stumble blocks notwithstanding, Google is hot in pursuit of state governments, taking lessons learned from LA and applying them to new contracts.Google Gets Back on Track in Big StatesAccording to a Google spokesperson, the company now has Google Apps government customers in 30 states. Last week, Google announced that the state of Wyoming is moving all 10,000 state government employees to Google Apps for Government and will be done with the migration in one year. Wyoming will be the first state in the country to have all state workers using Google, and it estimates the move to Google Apps will save taxpayers $1 million annually."The state of Wyoming's decision is the result of a two-year competitive evaluation process that included Microsoft," says Google spokesperson Andrew Kovacs.Also last week, Google announced that Multnomah County, the largest county in Oregon, has decided to move from Microsoft to Google Apps for Government with the goal of trimming $600,000 annually from the county budget. Multnomah County estimates it will save $100,000 in Microsoft licensing fees.Other major municipalities such as Washington, D.C. and Orlando, Fla., have moved to Google Apps this year to save money and improve communication and states such as Colorado, Iowa, Maryland, New York and Oregon are using Google Apps Education Edition in their high schools.Microsoft Steps It Up in California and New YorkBut if you think Microsoft is going to sit and watch Google take over the government sector, think again. Microsoft has made big investments in its BPOS cloud service that provides access to online versions of Exchange, SharePoint and Office Communicator (now called Lync) and is assertively going after state governments."Today, more than 500 state and local governments in the U.S. trust Microsoft Online Services to deliver the enterprise capabilities, security and privacy they require," says Gail Thomas-Flynn, Microsoft's vice president of state and local government.\n\nSlideshow: Windows Phone 7: Visual Tour of 10 Upcoming WP7 SmartphonesSlideshow: Seven New Windows 7 Tablets: In PicturesSlideshow: Windows 7 Hardware in Pictures: The Latest and Greatest Laptops\n\n\n\nIndeed, October was a good month for Microsoft's government play: the company secured large contracts to provide cloud-based e-mail and productivity apps to government workers in the states of California and New York, as well as Minnesota.Minnesota's move to BPOS concludes an 18-month project to consolidate e-mail systems such as GroupWise, Lotus Notes and Microsoft Exchange to a single cloud-based Exchange environment for 33,000 state employees.Microsoft's deal with the City of New York will consolidate several Microsoft licenses into one license, and allow 30,000 of the city's 100,000 employees to use Microsoft's BPOS cloud services for e-mail and productivity applications. New York City Mayor Michael Bloomberg said in a statement that the deal with Microsoft will "save $50 million over the next five years."In California, Microsoft will provide the state's 200,000 employees with cloud-based e-mail services through BPOS, thereby consolidating 130 different e-mail systems into one Microsoft cloud service. Is Microsoft Playing Fair?Google has accused Microsoft of rigging the game for certain government contracts. It protested the way California set up bids for the contract, according to an August 13 Los Angeles Times article, and claimed that the state had arranged the requirements in Microsoft's favor."There's no competition when only one team's allowed to play," Google's Kovacs said in the LA Times article.In an interview today, Kovacs said that the contracts in Minnesota and New York City were not open bidding processes, but rather "renewals of existing Microsoft contracts where Google did not have the opportunity to compete.""When there is an open competitive bid process, like in Los Angeles, Colorado and Wyoming," says Kovacs, "the majority of customers choose Google, and those that go with Microsoft get a great discount." Google is now going to greater lengths to ensure a level playing field. On Nov. 1, the company filed a lawsuit against the U.S. Department of the Interior, claiming that the DOI is "unduly restrictive of competition" because its bidding process for a contract worth $49.3 million over five years unfairly benefits Microsoft.Microsoft is not commenting on Google's accusations that Microsoft has received favorable treatment in state government bids.Though Google and Microsoft are in a slugfest in search and mobile, the government sector's movement to the cloud is standing out as the most intense clash between the two tech behemoths of late. Maybe that's because like any exciting election, this government race could be a dead heat. Shane O'Neill covers Microsoft, Windows, Operating Systems, Productivity Apps and Online Services for CIO.com. Follow Shane on Twitter @smoneill. Follow everything from CIO.com on Twitter @CIOonline. Email Shane at email@example.com.