Check with the hosting provider that your application is not being hosted on a load balanced server. If the server is being load balanced, your users will lose their session state information when the load balancer sends their request to another server. There are 3 settings Session State mode property:
InProc - Will store state information locally on the server from which the request is made (only effective when the application is being hosted on a single server in a non-load balanced environment)
StateServer - Allows a specially configured server to host state information for an entire web farm (I believe StateServer began to be offered on .NET Framework v2.0).
SqlServer - Allows a specially configured SQL Server instance to store session information for a web farm
[This information will vary slighty in a web garden scenario.]
See MSDN for more information on Session State.
This can happen very randomly based on their load balancing settings (think: sticky load balancing) and can work for several minutes one time and fail almost immediately another time.
The other possibility is the timeout property of the sessionstate setting in the web.config has been set to a low value (it is in minutes) and the session is expiring.