This is a weird problem. We have an item on the test server showing a 404 error page when you put in the URL key after the root URL (eg. www.mystore.com/url_key), however on our local machines they don't do this. I've even restored my local database so it's identical to the test server and it's not getting a 404.
The URL rewrites are identical, both my local machine and the test server has full page cache on.
Now, we could fix it by reindexing but we want to know the cause as to why the test server is showing a 404 while a local WAMP server doesn't.