Risolto:

Il problema non era nel LEFT JOIN ma nel WHERE, anzi nell'AND li ci voleva un OR.

E infatti modificando quel punto con WHERE categorie.visibile = 1 OR titoli.visibile = 1 tutto torna, come si vede nel risultato della query.

1 Fantascienza 4
2 Giallo 1
3 Interviste 3
4 Poesia 0
5 Pulp 0
6 Sentimentali 1