I have the same problem, but I am using a Nokia 3360. The format that you are talking about is called "canonical" and it is not supported by some phones (like mine). I haven't figured out yet how to change this format in Outlook (and I don't think is possible). What you need to do is to export your list of contacts to an external file, remove or modify the country code in that file and then synchronize against it. I know that it will represent an extra effort, but I am not aware of any other solutions. If you found one, would you please let me know? Thanks.