He made the comments at a partner briefing in Sydney this evening on the first day of his whirlwind Australian tour.
In the country for two days of talks with employees, major customers and the business community, Ballmer met a group of state government CIOs as well as federal health minister Tony Abbott earlier today.
A spokesperson for Abbott confirmed the meeting but declined to reveal further details.
Later, a typically-enthusiastic Ballmer addressed approximately 500 partner attendees, who grilled the CEO on all things Microsoft.
Asked about the future of Microsoft's .NET strategy, Ballmer admitted the platform's interoperability work with IBM and Sun had stalled slightly. But there would be a renewed .NET push, he said, and this was "an assigned priority" for the government sector.
"Government has really been pushing for stronger interoperability.
"We can't support open source, but we can support interoperability," he said.
Another partner complained of SQL Server's lack of spatial storage capabilities, saying the database was being beaten by Oracle.
This may be addressed in the next release [of SQL Server] in 18 months, Ballmer said, but conceded he "really didn't know".
A question on location-based services saw Ballmer plug Microsoft's "heavy investment" in mapping. But when a participant asked why MapPoint had not expanded to South East Asia so such services could be built, Ballmer was stumped.
"I didn't know we weren't doing well there," he said. "I'll address that with the team vigorously."
Microsoft's innovation was a constant theme throughout the 20-minute address. This would bring rewards for partners across the globe, including Australia, he said. "Our business in Australia will grow five to six percent over the next [financial] year."
Going after Google
Ballmer saved the best for last, firing a salvo at Google.
"What you're saying is, 'you're so far behind, why bother'?," he said when pressed to reaffirm Microsoft's commitment to search technology as it struggles to catch-up with Google.
"Well, if anyone thinks innovation is done in search, you're wrong.
"Does anyone here really believe search is going to look like it does now in 10 years?," he asked attendees.
He claimed Microsoft's long-term view was already making ground on Google.
"In the next six months, we'll catch Google in terms of relevancy," he said.
Search has more relevance than just the desktop, he said, reiterating Microsoft's well-known stance . "It's important for people who search a corporate network," he added.
"We'll use search to peer into a range of business applications which would allow multiple applications to be searched simultaneously.
"Take for instance the Siebel database. Now I've never used that interface. But I'd love to go to it and say 'who is the account manager for the Commonwealth Bank of Australia?'," Ballmer told the partners.
Microsoft's vision for search would eventually make such data discoverable, without using the [actual] application.
"This is important for our customers, but also in joining the battle with Google!
"Give up the fight? No, never," he said.