Tanto é correcto deve haver como deve de haver, mas não é indiferente empregarmos ou não empregarmos a preposição de. Vejamos então:

1. Empregamos dever de + infinito, quando indicamos probabilidade, suposição. Eis um exemplo de «Os Lusíadas» para mais fácil compreensão. Transcrevo toda a estância do Canto I, 24:

Eternos moradores do luzente,
Estelífero Pólo e claro Assento,
Se do grande valor da forte gente
De Luso não perdeis o pensamento,
Deveis de ter sabido claramente
Como é dos Fados grandes certo intento
Que por ela se esqueçam os humanos
De Assírios, Persas, Gregos e Romanos.
Outro exemplo, este de José Régio em «As Encruzilhadas de Deus», pág. 100:
Quando a manhã nasceu
Eu devia de ter um vago olhar louco.

Devemos empregar dever + infinito, sem a preposição de, para indicar certeza, obrigação; precisão dum resultado. Eis um exemplo de Camões, «Os Lusíadas», X, 155:

Para servir-vos, braço às armas feito;
Para cantar-vos, mente às musas dada;
Só me falece ser a vós aceito,
De quem virtude deve ser prezada.

Todos nós dizemos assim: Ó Mário, olha que tu não deves fumar! Bem sabes que isso faz muito mal...

O Novo Dicionário Aurélio da Língua Portuguesa (1997) ensina que dever, seguido da preposição de e de um verbo no infinitivo, indica probabilidade, suposição: (…) "Deve de chover hoje" . Mas acrescenta: "O uso moderno da língua pouco atende a essa peculiaridade; assim, é mais comum que se diga, com a mesma acepção, deve chover hoje". Em Portugal, a ausência do de também é mais corrente, e até sentida como mais correcta.