I'm thinking that normalization is off a bit, are you normalizing all numbers in your dial plan to E.164 first? If you phone company wants to see them in a different format, I'd make that manipulation at the trunk, IP gateway, or SBC level.
Please remember, if you see a post that helped you please click "Vote" on the left side of the response, and if it answered your question please click "Mark As Answer".
SWC Unified Communications This forum post is based upon my personal experience and does not necessarily reflect the opinion or view of Microsoft, SWC, their employees, or other MVPs.