I had this problem – only happening to non-admin users and mainly in IE – and I found these threads helpful:
http://stackoverflow.com/questions/6752773/the-webpage-cannot-be-found-http-404-randomly-and-only-in-ie9-windows-7
http://serverfault.com/questions/251673/getting-404s-on-wordpress-site-but-only-from-ie-with-friendly-error-messages-tu
The workaround to set the status header manually to 200 worked on my site (though at some point I should work out what it is in the theme that’s causing it and fix it properly).
