Irrecoverable Error "Could not find valid Key" when using Civicontribue contribution page as anonymous user

I have been having the following error appear when I use a contribution page as an anonymous user:

Sorry. A non-recoverable error has occurred.
Could not find valid Key

Essentially, every once in a while an anonymous user visits the contribution page and their `session` field in the drupal sessions table is empty. When the contribution page works perfectly the `session` field is properly populated with "CiviCRM|a:1:{s:8:"domainID..."

I think this is similar to the closed issue at: http://issues.civicrm.org/jira/browse/CRM-1894

Here is my setup:

Drupal 5.1
CiviCRM 1.7.9379
mySQL 4.1
PHP 4.3.9-3.22

For the sessions table I have the following:

[code]
CREATE TABLE `sessions` (
`uid` int(10) unsigned NOT NULL default '0',
`sid` varchar(64) NOT NULL default '',
`hostname` varchar(128) NOT NULL default '',
`timestamp` int(11) NOT NULL default '0',
`cache` int(11) NOT NULL default '0',
`session` longtext,
PRIMARY KEY (`sid`),
KEY `uid` (`uid`),
KEY `timestamp` (`timestamp`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
[/code]

I have the following base url settings. I do not have the absolute url because I am running SSL pages for contributions. Not sure if this makes a difference.

[code]
define( 'CIVICRM_UF_BASEURL' , '/' );
[/code]

[code]
$base_url = '';
[/code]

Here are my findings so far. I used firefox to administer and flush drupals' cache, and I am using IE to test a contribution membership page as an anonymous user.

I opened phpmyadmin and browsed the sessions table while I cleared the drupal cache as well as the IE cache. I then Emptied the sessions table. Then I visited the contribution page as an anonymous user.

On some occasions the database's session field is blank, and when it is and I click "Continue >>" on the contribution page I get the "Could not find valid Key" error.

I wish I knew more, or could help debug, but I'm not a programmer.