Phone number normalisation standards -- help?

I had an email in from a reader who heads up the helpdesk at a large FTSE. Here’s his challenge:

Dear Ewan,

We’re in the process of normalising our phone numbers in our active directory structure. Right now, all our numbers are formatted +44 (0) 123 456789.

A few years ago, this standard was fully tested and every single handset we could find worked perfectly with this structure. However, in recent months, we’ve adopted lots of new technology — including iPhone, Android and some of the latest BlackBerries. Now and again, we get support calls from users complaining that they are unable to dial numbers from the Global Address List. We have noticed that these users happen to have iPhones and Android devices.

Do you know what the correct standard across different platforms is? e.g. +44 123 456789? Do you know of any other work-arounds for this issue?

Do we need to go through the whole directory and change every single field (removing that errant zero) or is there a piece of software that will do this for us?

I’d very much appreciate any suggestions,

Regards
Ed