I would imagine that if your users can just refresh the page to become logged back in, that they're almost certainly not being logged out in the first place. Far more likely that they're being served a cached version of the page.
Consider this situation:
- User visits home page as an unauthenticated user
- Cache headers tell the browser to keep that page for at least x minutes before refreshing
- User visits the login page and authenticates.
- User re-visits the home page
- The browser cache kicks in, and the user is shown the cached version of the home page they saw the first time round
- User refreshes the page - the browser cache is cleared, and they now see the index page as an auth'd user
There must be a logical explanation and definitive way to stop it, surely?
Absolutely there will be - but you need to identify which part of your setup is responsible for the problem. As described above, it's probably a caching issue, so that's where you debugging should concentrate. I've seen this sort of behaviour more often when a reverse proxy is in front of Drupal, so if you have one enabled, start debugging that first.
If you're not comfortable debugging caching issues in that manner, you'll really need to hire someone who is to do the job. It's not something you can do half-heartedly, or without a reasonable knowledge of caching in general (not just in Drupal). If you happen to have a Pantheon account, ask them about it - they plugged the same bug in their Varnish config some time back (I have no idea how though, didn't ask).
I'm not sure that any more specific advice can be really be given, without having access to the server. I'm by no means a caching ninja though, so maybe someone else will be able to offer a specific part of config you can change, test you can do, etc.