The user is a key part of the solution
Although I am in a very small company, we've been on the leading edge (sometime bleeding) of mobile communications use for well over a decade. And we have had minimal problems with our service over this time - even though we upgrade technology at least on an annual basis.
I feel that the reason is that our staff ("users") are "part of the process" - not simply dictated to by IT and Accounting.
I treat our user community as adults. That means that I (as CIO) discuss their needs with them, listen carefully to what they want and what their issues are, then provide a list of solutions that covers their needs. Things like security, confidentiality, improper use of corporate assets - these are open and thoroughly explored, with feedback from the users individually as well as a community incorporated into our mobile technology planning. And it has paid off handsomely for us: our users understand the fundamental issues we're addressing from the company standpoint and have been remarkably resistant to misuse of corporate resources - mainly because we insure that the company takes care of their personal needs as well. We have a consistent set of policies that cover ALL aspects of personal communications, most of which reflects the user's requirements as well as the common corporate goals.
We use a single carrier (SPRINT) for all our devices, and this is pretty much the only restriction. All of our users have new (< 1 year old) multi-media devices with full 3G capability, and are subscribed on unlimited or nearly unlimited usage plans. We let the users choose their own device - as long as it meets the minimum corporate requirements I don't have a problem with it - and as adults they are aware of what their responsibilities are in choosing and using the device. (I have Blackberry, Palm, WM5 and Motorola based devices in the mix and so far with 10 years of allowing this I've had only minor issues to deal with - usually carrier issues at that.) We run our own email and data services and do not use Exchange, so many security problems are eliminated right there, and other issues (like ringtone purchases, games, etc.) were eliminated by educating the users on how to use alternative tools (like rip and download their own music to their phones) which they actually prefer to the wonky vendor-supplied commercial sites.
Yes, it costs more per month to do this. Probably double per user what most companies pay for mobile solutions. However, our pay-back is measured in simplified accounting (consistent costs), near 100% availability of staff 24/7, and a user community that actively works to improve the way these services work in our business. And we consistently delight our customers by being able to leverage this technology to help us provide better service.
Summarizing: if you treat your staff as adults, allow them to drive the technology with open education and feedback and a minimal set of standards that give them a lot of choice you can eliminate the "control" problem and get deep and broad use of the technology - which, after all, is the whole point of having it...