hay dos formas, la forma obstrusiva es agregar el evento onChange a cada select en el html (sucio, pero funciona) y lanzar una funcion, la otra es registrar los eventos de cada select... y para esta hay 2 formas xD usar jquery o hacerlo a la brava con esto, si te decides por la ultima te recomiendo leas esto

como quieras lo unico que debes comprobar es cual cambian (combo1 o combo2) llamemosles ob1 y ob2 (los creas con document.getElementById('id del objeto') )

y luego deshabilitas en uno el que se selecciono en el otro xD para eso hay tambien 2 formas eliminando del DOM o agregando disabled='disabled' a la opcion que eligio en objeto contrario (espero me entiendas x'D prefiero explicar que pegar un codigo)

pondre la de jQuery y deshabilitando (no eliminando) que seria el mas facil x'D no tengo tiempo ademas me encanta jQuery xD

$('combo1').change(function(){
    $('combo2').children('select[value='+this.value+']').remove();
});

o algo asi xD pruebalo que lo escribi en el aire jajajaja ojala se te ilumine el foco para hacer algo mas generico en base a esto