I fought with this very issue, and found that I was dealing with two different domains. Some of my users were starting out on mydomain.com and then after finishing with the payment provider they were getting redirected back to www.mydomain.com. This would result in a completely new session.
Possible that this is your issue?
If so, I would stick something like this early on in the bootstrap process, possibly right at the top of your index.php file:
if($_SERVER['SERVER_NAME'] != 'www.mydomain.com') {
Header("Location: http://www.mydomain.com" . $_SERVER['REQUEST_URI']);
exit;
}
This assures right up front that users are using the domain that you want them to use. The redirect will preserve the full url, with any GET variables.