We have recently had an issue with a weird 404 page in Magento. Basically, when accessing to some stores, we got a 404 page: but not the 404 page when a page doesn’t exist. It was a 404 Magento page, different than the ordinary ones.
After investigating we have finally found that the problem was with the SET_ENV variable. We have set up this in the server configuration. But the code we where applying didn’t exist in Magento. That’s why Magento was saying that the page didn’t exist. Instead of saying that «that store code doesn’t exist».