少しデバッグして、実際に自分の答えを見つけました。

change イベントは発生しますが、要素が選択されていない場合、jquery val() は空の配列ではなく「null」を返します。それを機能させるには、null と比較するだけで十分です。

$('#multiselect').change(function(){
    var selecteditems = $(this).val();
    if(selecteditems===null){ $('#selectedversions').text('none'); }
    else{ $('#selectedversions').text(selecteditems.join(',')); }
});