Em português geral, é Natal sem artigo, por ser cidade e a maioria das cidades não fazer uso do artigo, com poucas exceções (Rio de Janeiro, Porto, Cairo e mais algumas poucas). Note que no verbete natalense do Dicionário Houaiss se lê «a Natal», sem artigo definido: «adj. 2 g. s. 2 g. (1599) relativo a Natal, capital do estado do Rio Grande do Norte, ou que é seu natural ou habitante.»

No entanto, acho que se deve agir com tolerância com quem é dessa cidade e a vida toda usou o artigo, que constitui um uso localizado.

Veja a posição deste professor, que parece ser natural de lá. Também é interessante notar a presença do artigo no portal da prefeitura dessa cidade.