Antes de cargar las nuevas poblaciones al cambiar de provincia, elimina todos los hijos del select y antes del bucle que rellena el select incluye un elemento en blanco y punto pelota.
Lo del span dentro de un select es una barbaridad, para agrupar las opciones existe el
optgroup, pero no es lo que necesitas.
para eliminar todos los elementos del select
Código:
document.forms.formulario.camposelect.options.length = 0;
o bien
Código:
document.getElementById('camposelect').options.length = 0;