Obviously, it's not a case of things not working, it's how the number looks on the set.
I question why your provider is adding an extra zero when numbers sent already seem have a leading zero. Although I'm not sure if this is the case with all incoming numbers.
I know in North America some providers, will prefix some numbers with a one (the standard long distance access prefix). This can sometimes be if the number is considered long distance and requires dialling the one, and other times it is there for no apparent reason, even on local numbers, most likely because the call originated from another provider. The problem for us is that local calls, will not go through if the one is added to the number. The local (PSTN) provider cannot do anything about formatting numbers that are sent to then "as is" with a leading one.
You provider may be in the same situation where caller Id, from other areas (providers) may not have a leading zero. In their case they add the zero, just to be on the "safe" side even if it means you get a number that starts with two zeros. They may even have enabled the ability to accept calls in that format.
If you haven't done so, you may still want to have a chat with them to see if there are options available at their end.