This just plagued me for a few days. We had a working dev-staging-production workflow and we started getting 404s on only the production system, but the pages still rendered. This lead to a nightmare situation where to us the site was functional, but google began dropping our page results.
We were getting 404s on all of the aliased urls (which are handed to drupal by this line in the .htaccess):
ErrorDocument 404 /index.php
After much digging around, cloning, even php xdebugging, it turned out that the production apache VHost config was not allowing overrides for the drupal root dir, so even though all of the .htaccess directives were placed in the VHost config, apache wasn't considering directives contained further down the filesystem.
However that in itself doesn't explain the problem because we had no additional .htaccess files further down the file structure, save for the default drupal files dropped in the sites/default/files[/public] directories, and 2 libraries. They had nothing to do with the 404s.
So, perhaps this is another cause. I'm still at a loss as to:
A. Why this happened suddenly with no apache configuration changes, system package updates, or drupal module updates (pathauto_persist was upgraded recently to 7.x-1.4 but after downgrading the problem 'persisted').
B. Why opening up the AllowOverride fixed it.