LEFT JOIN não retorna todos os registros da tabela do lado esquerdo

O problema pode ser que você esteja filtrando na tabela unida usando a condição where que filtrará também os serviços do departamento que não têm uma correspondência na junção, mova a filtragem na junção e deixe apenas os filtros em d na cláusula where:

SELECT d.mt_code,
   d.dep_name,
   d.service_name,
   COUNT(t.id)
FROM DepartmentService AS d
LEFT JOIN tbl_outgoing AS t 
  ON d.mt_code = t.depCode 
    AND t.smsc = "mobitelMT"
    AND t.sendDate BETWEEN '2014-07-01' AND '2014-07-02'
WHERE d.service_type = 'MT'
GROUP BY d.mt_code

Para explicar por que isso acontece, mostrarei o que acontece com sua consulta e com minha consulta, como conjunto de dados, usarei isso:

states
 ____ _________ 
| id | state   |
|  1 | Germany |
|  2 | Italy   |
|  3 | Sweden  |
|____|_________|

cities

 ____ ________ ___________ ____________
| id | city   | state_fk  | population |
|  1 | Berlin |        1  |         10 |
|  2 | Milan  |        2  |          5 |
|____|________|___________|____________|

Primeiro vou analisar sua consulta.

SELECT s.id, s.state, c.population, c.city
FROM states s
LEFT JOIN cities c
ON c.state_fk = s.id
WHERE c.population < 10

Então vamos passo a passo, você seleciona os três estados, esquerda junta com cidades terminando com:

 ____ _________ ____________ ________
| id | state   | population | city   |
|  1 | Germany |         10 | Berlin |
|  2 | Italy   |          5 | Milan  |
|  3 | Sweden  |       NULL | NULL   |
|____|_________|____________|________|

Você filtra a população usando WHERE c.population < 10 , neste ponto, sua esquerda com isso:

 ____ _________ ____________ ________
| id | state   | population | city   |
|  2 | Italy   |          5 | Milan  |
|____|_________|____________|________|

Você perde a Alemanha porque a população de Berlim era de 10 mas você também perdeu a Suécia que tinha NULL, se você quisesse manter os nulos, você deveria ter especificado na consulta:

WHERE (c.population < 10 OR IS NULL c.population)

Que retorna:

 ____ _________ ____________ ________
| id | state   | population | city   |
|  2 | Italy   |          5 | Milan  |
|  3 | Sweden  |       NULL | NULL   |
|____|_________|____________|________|

Agora minha consulta:

SELECT s.id, s.state, c.population, c.city
FROM states s
LEFT JOIN cities c
ON c.state_fk = s.id
  AND c.population < 10

Antes de juntar os dois, filtramos as cidades da tabela (usando o AND c.population < 10 condição após o ON ), o que resta é:

 ____ ________ ___________ ____________
| id | city   | state_fk  | population |
|  2 | Milan  |        2  |          5 |
|____|________|___________|____________|

Como Milão é a única cidade com população menor que 10, agora podemos juntar as duas tabelas:

 ____ _________ ____________ ________
| id | state   | population | city   |
|  1 | Germany |       NULL | NULL   |
|  2 | Italy   |          5 | Milan  |
|  3 | Sweden  |       NULL | NULL   |
|____|_________|____________|________|

Como você pode ver, os dados da tabela à esquerda permanecem porque a condição de filtragem foi aplicada somente para a tabela de cidades.

O conjunto de resultados muda dependendo do que você deseja alcançar, se, por exemplo, você deseja filtrar a Alemanha porque Berlim tem população menor que 10 e manter a Suécia, você deve usar a primeira abordagem adicionando o IS NULL condição, se você quiser mantê-lo, você deve usar a segunda abordagem e pré-filtrar a tabela à direita da junção esquerda.