Así, muy rápido se me ocurre esto.
SELECT tabla.Provincia,count(conDatos.Provincia)
FROM tabla LEFT OUTER JOIN
(select distinct Provincia from tabla WHERE tabla.Telefono LIKE '666%') conDatos ON
conDatos.provincia=tabla.provincia
group by tabla.Provincia
order by Provincia
http://sqlfiddle.com/#!18/470c1/1