I have had this issue for a long time. I have tried to trouble shoot it, but things start working and I think it is done. I just updated to the latest WordPress SEO and it happened again. I also can not use sitemap, because randomly the blog posts will go 404 not found. I have not found any information to what is causing this but I know it is something with or conflicting with WordPress SEO.
This means no one can read the blog. I have had this issue with two other sites. This has happend to clients and I have removed the plugin for them.
Any suggestions? I feel I have tried everything.