É corretíssimo. Todo dia—todo o dia em Portugal—é usado com o significado de ‘todos os dias, cada dia’ há séculos. Pelo menos desde o século XIII segundo o dicionário Houaiss (Lisboa, 2002), cujas partes relevantes cito, desenvolvendo algumas abreviaturas; a aceção relevante é a segunda:
todo /ô/ adjetivo (sXIII cf. FichIVPM) 1 a que não falta nenhuma parte; inteiro completo, total <todo o dia foi de chuva> <toda a família se reuniu ali> ■ pronome indefinido 2 (século XIII) qualquer, seja qual for; cada <todo o cidadão tem direitos e deveres> […] GRAMÁTICA […] b) é de se notar a diferença, especialmente na norma brasileira, entre todo o e todo, respectivamente, acepções 1 e 2: todo o dia ( = o dia inteiro) foi de chuva; todo cidadão ( = qualquer cidadão) tem direitos e deveres (mas aqui, tratando-se do plural, é obrigatório o uso do artigo: todos os cidadãos têm direitos…); na norma europeia, o artigo é geralmente usado em ambos os casos
Este uso é análogo ao de muito dia com o significado ‘muitos dias’—passei muito dia sem comer—objeto desta pergunta e desta outra ou ainda ao de tanto dia com o significado de ‘tantos dias’. Como já se viu no Houaiss, este uso aplica-se em princípio a qualquer nome contável:
Todo (o) cidadão tem direitos e deveres.
Todo (o) casal precisa de privacidade.
Toda (a) criança tem direito à educação.
Ao que parece, no português antigo usava-se a expressão indiferentemente com e sem artigo. Ver este extensíssimo artigo sobre o assunto no Gramaticalhas. Mas parece que o uso sem artigo, distinguindo todo dia (‘todos os dias’) e todo o dia (‘dia inteiro’), já foi recomendado no século XVI por Damião de Gois. Parece ter sido também a opção de Luís de Camões (Os Lusíadas, Canto I, 2ª estrofe, 1572):
[…] Cantado espalharey por toda parte,
Se a tanto me ajudar o engenho & arte.