I use modRewrite to make URLs like:
But I've noticed lately that the Google Webmaster Tools is finding a lot of pages that don't really exist. For example, privacyPolicy.php resides on the root, and yet Google thinks it resides on example.com/stories/privacyPolicy.php, therefore its throwing 404 errors. And they are starting to accumulate quickly:
Would this best be resolved by changing my footer links to use the full URL? Like http://www.example.com/privacyPolicy.php.
Its probably because you are using relative link. You should use either root absolute or FQD absolute. Or even using the base html element would work.