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.
Best Answer
One explanation is your .htaccess isn't being picked up. Can you try to add in index.php in the URL and see if this solves the issue?