Prueba haciendo ambos joins con left
Código:
SELECT DISTINCT TLocalidad.IdLocalidad, TLocalidad.Localidad FROM TLocalidad LEFT JOIN TResPublica ON TLocalidad.IdLocalidad = TResPublica.IdLocalidad AND TLocalidad.IdProvincia = TResPublica.IdProvincia LEFT JOIN TListPrivadas ON TLocalidad.IdLocalidad = TListPrivadas.IdLocalidad AND TLocalidad.IdProvincia = TListPrivadas.IdProvincia WHERE TLocalidad.IdProvincia =45 ORDER BY localidad