Seems like an issue with the Salesforce Session Cookie. You could use something like the Chrome developer tools Network tab to inspect the cookies that are sent to the Visualforce page.
At a guess, your older Admin Session cookie is being sent with the first request. Once refreshed to correct use cookie is sent.
Another possiblity if you are using SAML SSO:
Insufficient Privileges when logged in as another user - Knowledge Article Number: 000175641
Description
User has implemented a SAML SSO solution from Salesforce to an external Java app using Salesforce as the identity provider.
We're using the FederationIdentifier field from the standard User
object in the SAML assertion. The solution works great when a user is
logged in as him/herself, but it doesn't work when a user is logged in
as another user and giving Insufficient Privileges error.
Insufficient Privileges
You do not have the level of access necessary to perform the operation you requested. Please contact the owner of
the record or your administrator if access is necessary.
Internal Diagnostics:
Cannot use IdP while SU'd as another user system.security.NoAccessException: Cannot use IdP while SU'd as
another user
Resolution
The error message explains it nicely : We actively block SSO logins when you are logged in as a different user. 'Login as' is
meant to enable Salesforce admins to support their salesforce users
but it can definitely not be used as a 'backdoor' to gain access to
other systems as that user. That would be a huge security hole no.