Here is what seems to be the answer to this question (taken from a comment from OPer below the question):
I'd forgotten to enable mod_rewrite and mod_headers! What I was amazed about was that clean URLs were working at all without them. I think this is because .htaccess points 404s to Drupal, which will then interpret the requested URL and show the appropriate page, but of course Apache is sending a 404 header.