Acabou que mod_rewrite não foi ativado.
Em /etc/httpd/conf/httpd.conf
, comentário:
#LoadModule rewrite_module modules/mod_rewrite.so
Por que eu não encontrei isso no começo? Porque toda a reescrita do URL parecia funcionar bem, exceto pelo cabeçalho 404.