The problem I was having is due to the use of double-quotes to delimit the search terms. While searches on a single taxonomy will work with double-quotes, searches on multiple taxonomies only work with double-quotes.
This works:
[documents doctype=’work-inst’ department=’web’]
This may be either undocumented but intended behavior, or a subtle bug in wp_query().
