[SalesForce] Site goes “Under Construction” or “Unauthorized” until Page is Viewed Internally with “/apex/…”

I have been experiencing very odd Site behavior the past 3 days. Whenever a Change Set is deployed with Controllers/VF Pages used in the Site or even at other "random" times, users are redirected to the "Under Construction" or 'Unauthorized" Pages. If I go to an affected Page internally via /apex/MyAffectedPage, the Page will then be available externally on the Site.

The Site's Active Home Page is never affected. If viewing a Page externally, and it redirects to Under Construction Page, visiting any other Page (except for the Site's Active Home Page) will redirect to Under Construction Page. But if I view a single Page internally, the Page will then be available externally, but every other Page (except for the Site's Active Home Page) will redirect to Unauthorized Page instead.

I went to "Preview as Admin" in the Site when I was getting redirected to the Unauthorized Page, and I think it was showing an "api is not accessible" message. I have to wait for the issue to occur again before I can confirm this.

If the issue strikes, I need to visit every Page used in the Site to have the entire Site available externally again.

This is terrible because we're finding out the issue happened when our clients complain our Site is down. I am adding custom Under Construction and Unauthorized Pages that will email us whenever it's viewed so we can cut our response time down, but I don't have the slightest clue on how to fix the issue altogether. Somehow viewing the Page internally is changing something in the Salesforce Back-end which allows the Page to be viewed externally. And what could be the trigger which resets the Page's external access?

About the "random" events causing the issue: They happen less than a few times a day, and the last event happened overnight. Maybe it was triggered when Salesforce was resetting the 24 Hour Site Usage Limit.

Additional Exceptions: The Site has been very buggy. I've ran into the "api is not accessible" Message every now and again over the past couple of days. I deployed a Change Set, visited all the Pages and verified it was externally available, and then, a couple hours later, I got a "Class needs to be Compiled" Exception with "api is not accessible" being the root cause. I clicked "Compile All Classes" under Setup –> Apex Classes, and the issue was resolved. I've hardly ever ran into that issue, and it seems very odd that now it happens with the other issue.

Update

On Friday, the Site was up and running fine all day. A minute ago, I checked the Site as an Admin, and I got the "Under Construction" Page. Since I was viewing the Site as an Admin, it displayed the error:

Entity is not api accessible

I went to Setup –> Develop –> Apex Classes and clicked Compile All Classes. Then I checked the Site again, and every Page was up and running.

Everything was running fine Friday night. No Change Sets were deployed over the weekend. But Salesforce did use their Service Window Sunday morning…

Any ideas?

Another Update on 2015-08-03

Ran into this issue again this afternoon. I tried Compiling All Classes, but it didn't work this time. I had to go into each Page internally via /apex/... so the Page would be available externally.

Update for 2015-08-06

We ran into the Under Construction Error 2 out of the last 3 days. It seems to occur at most once a day unless we deploy a Change Set which always triggers the issue.

Update for 2015-08-23

The issue still occurs about once, maybe twice a day and then also every time we deploy a Change Set. We've been working with Salesforce Support for about two weeks, and the best idea so far is that the "Entity is not Api accessible" Exception occurs when the Site's Metadata are not all the same API Version. So, I updates all my classes and VF Pages to API v34.0, but the issue has still happened since then.