Thank you for the bug report! There are a bug in clearToolbar in the lines of the code. I will report the bug later to trirand.
To fix the problem one have to use beforeClear callback of filterToolbar:
beforeClear: function () {
    $(this.grid.hDiv)
        .find(".ui-search-toolbar .ui-search-input>select[multiple] option")
        .each(function () {
            // unselect all options in <select>
            this.selected = false; 
        }
    );
    $(this.grid.hDiv)
        .find(".ui-search-toolbar button.ui-multiselect")
        .each(function () {
            // synchronize jQuery UI Multiselect with <select>
            $(this).prev("select[multiple]").multiselect("refresh");
        }
    ).css({
        width: "98%",
        marginTop: "1px",
        marginBottom: "1px",
        paddingTop: "3px"
    });
}
The demo demonstrates the workaround. If the bug in jqGrid will be solved then one could remove the first tree lines from the beforeClear callback like in the demo.