Turns out that those libraries were
provisioned by code, and the code set a property on the library called "AllowEveryoneViewItems" (msdn documentation). This property, when set to true, means that anyone- even unauthenticated users, will be able to download and view items in the list or library - even without permissions.
The reason to turn it to true is when dealing with anonymous sites - for example, if you have an internet site and you want to put links to documents from pages, but you don't want users to be able to browse the library itself.
We troubleshooted several ways and couldn't find the solution...until we noticed something weird when we were looking at the content type schema - the taxonomy field was set to support multiple values! our code was specifically written for that field, which is not supposed to support multiple values. Some nasty little elf went into the column setting in the library and changed my precious from its normal settings. Setting it back and everything went to normal.
Moral of the story - since setting a taxonomy field's value in code is different if the field supports multivalue or not, make sure either your code is robust enough to handle a nasty user making a change, or tell your users to keep their hands to themselves!
