Random Invalid Viewstate Error
A couple of possibilities to investigate:
Update panels are changing form field values (which are what is used to compute ViewState), then the page gets POSTed back to the server, where the new values make validation fail. See this post
You have caching enabled (perform a trace of HTTP headers - make sure you don't have dev tools open) which is causing invalid ViewState to be generated w/ UpdatePanel gumming things up.
Are you using Server.Execute anywhere? (see above link for same)
(less likely) Does your "Virtual Private Server" get migrated to different hardware (perhaps without you knowing it)?