As locuções de baixo de e debaixo de são ambas corretas, sendo utilizadas em contextos diferentes.

Debaixo (de) funciona como simples preposição, tendo um sentido equivalente a sob:

(1) «Os livros ficam debaixo da mesa.» (= sob a mesa)

De baixo (de) é introduzido pela preposição de, que é pedida por uma palavra anterior, como se pode observar através do contraste entre as frases (2) e (3) nas quais se percebe que a preposição de é regida pelo verbo vir:

(2) «O gato vem de baixo da cama.»

(3) «O gato vem do quarto.»

Uma outra diferença entre as locuções tem a ver com os sentidos que estas expressam. Assim, debaixo (de) responde, na frase, à questão onde:

(1) «Os livros ficam debaixo da mesa.» = «Os livros ficam onde? Debaixo da mesa»

Por seu turno, a locução de baixo (de) responde, na frase, à questão de onde:

(2) «O gato vem de baixo da cama.» = «O gato vem de onde? De baixo da cama.»

Neste contexto a preposição de «marca o lugar no qual se origina o movimento e o afastamento relativamente a esse lugar» (Raposo et al., Gramática do Português, p. 1548), ou seja, o gato realiza um movimento que teve início sob a cama e que evoluiu no sentido do afastamento.

Tendo em consideração o que ficou dito e em resposta à questão colocada, a locução a utilizar na frase apresentada será de baixo de:

(3) «Ele saiu de baixo da mesa.»