Um número de telefone pode começar com 0?

Do ponto de vista do encaminhamento telefónico, não. Um número de telefone como visto dentro da central telefónica é uma sequência de dígitos que não começam com zero. Os primeiros de um a três dígitos são o código do país. Tudo isto é definido na recomendação E.164 da ITU (União Internacional de Telecomunicações): E.164 - Wikipedia

Então, por exemplo, o número de telefone para 10 Downing Street (residência do Primeiro Ministro do Reino Unido) como visto dentro das centrais telefônicas é 442079250918.

O zero principal em muitos números de telefone no mundo é informar à central telefônica que este não é um número curto que é implicitamente prefixado com o código local do país e da área. Uma central telefônica também pode detectar outros códigos após o 0 principal, como um segundo 0 (na Europa) indicando que o número seguinte é um número completo incluindo o código do país e não um número nacional implicitamente prefixado com o código do país. É por isso que dentro do Reino Unido você marcaria 02079250918 para tentar falar com a Sra. May. Isso é 0 para indicar que você está discando um número nacional do Reino Unido, e depois 2079250918. Dentro da rede telefónica isto é passado e gravado como 442079250918 embora normalmente seja mostrado para si, se tiver o identificador de chamadas (ou usar um telemóvel) como 02079250918. Isto é, se a Sra. May lhe ligar do número 10 de Downing Street.

Se quiser ligar para outro número internacional, talvez para a Casa Branca dos EUA, a partir de um telefone do Reino Unido você ligaria para 001202456111111 e a central telefónica interpretaria isto como "número de telefone completo... com código internacional... 12024561111" e gravaria como 12024561111.

O padrão de telefone celular GSM, e seus sucessores, define + como um prefixo para o usuário mostrar que o seguinte número é um número de telefone completo, incluindo o código do país. O + também é definido em E.164. É por isso que você pode digitar +12024561111 no seu telefone celular para tentar ligar para a Casa Branca e ele funcionará em qualquer lugar onde seu telefone estiver conectado a uma rede GSM, não apenas dentro do Reino Unido.