Bem, isso é embaraçoso. Fiquei pensando que a ordem negar, permitir significava que a lista era tratada como uma regra de ACL ou firewall quando na verdade não era. A última regra sendo "Permitir de todos" cancelou tudo que eu neguei. A configuração correta é esta:
BrowserMatchNoCase "^bingbot" block_spider
BrowserMatchNoCase "^msnbot" block_spider
<Proxy *>
Order Allow,Deny
Allow from all
Deny from env=block_spider
</Proxy>