During form validation, can you "stash" a form for an end user while they fill out a different form?
I just looked at your Entity Availability project page, and it looks interesting. You are facing the classic Temporal dependency problem of all scheduling systems (eg Departure time depends on Arrival time). This is the one data dependency which cannot be resolved statically.

The Webforms module uses $_SESSION to store information for multi-page forms for the anonymous user. In the case of the Webform module, the submission ID ($sid) is saved the $_SESSION, and the $form_state is saved in and retrieved from the database, however I see no problem with using $_SESSION to maintain a working copy of the $form_state object ($_SESSION['form_id'] = $form_state;). However, I would suggest you look at a cache_entity_availability table keyed on, perhaps, form_id and uid, just in case the session expires (servers down, network problem etc).

Thanks for the additional info, and good luck with the project.