I have this problem and maybe it's something really obvious, but I have not been able to figure it out.
I'm working on a form api form on Drupal 6, and for some reason on my development machine (my local computer), on which I'm using xampp, the $form_state['storage'] NEVER persists. On the rebuild of a form (e.g. going to the second page), the key is just not there and I lose key information from the first page (and from elsewhere). Does anyone have any insight into this? It seems to persist into the submit handler from the first page, but doesn't make it to the rebuild.