Cita: El problema es que la columna departamento es de tipo INT(11), y al compararla con cualquier cadena que no sea un número, me devuelve aquellos nodos cuyo departamento es 0
Creo que esto es parte del problema. El 0 en el ámbito numérico es en realidad un valor por defecto. No deberías asignarlo a ningún departamento, como pareces haber hecho. Si haces la conversión de una cadena de texto que no tenga forma de fecha, te saldrá NULL, y eso es lo que debería salir, pero si no se acepta NULL, el valor por defecto es el 0. Y ese nunca debería ser un valor asignado porque no estaría siendo un identificador único de ese departamento, al ser identificador de todos los que no tienen identificador. Se recomienda que nunca un foreign key sea NULL, y también debería recomendarse que tampoco lo fuera el 0. Y trataría de cambiar ese primary key 0 y foreign key 0 a otro número.