How to detect when $form_state data have expired (and gotten deleted)?
Although this arrangement is probably more complicated than it needs to be, here's how I was able to achieve it. I'd be happy to accept another answer if someone has a more elegant solution.

/**
 * Implements hook_form().
 */
function my_module_form($form, $form_state) {

    if (isset($form_state['storage']['elements_to_append'])) {
    // If other functions want us to add elements to the form:
        $elements = $form_state['storage']['elements_to_append'];
        foreach( $elements as $key =&gt; $element ) {
            $form[$key] = $element;
        }
    }

    $form['submit'] = array(
        '#type' =&gt; 'submit',
        '#submit' =&gt; array(
            'my_module_submit',
            'my_module_submit_safety',
            // ^ Depending on your requirements, you may wish to switch the
            // run-order of these two functions. Having my_module_submit_safety()
            // put first prevents subsequent actions in the case that $form_state
            // was lost since last navigation, but your users may lose more pages
            // of work before this check becomes effective; it's a tradeoff
            // either way unless you want to run the safety-check twice.
        ),
    );

    return $form;

} // my_module_form() OUT

/**
 * Implements hook_submit().
 */
function my_module_submit($form, &amp;$form_state) {

    $form_state['rebuild'] = true;

    $form_state['storage']['elements_to_append']['navigated'] = array(
        '#type' =&gt; 'hidden',
        '#value' =&gt; 1,
    );

} // my_module_submit() OUT

/**
 * Implements hook_submit().
 */
function my_module_submit_safety($form, &amp;$form_state) {

    $form_state_cid = '';
    if (isset($form_state['input']['form_build_id'])) {
        $form_state_cid = 'form_state_' . $form_state['input']['form_build_id'];
        // ^ This is effectively the same way the CID is built in @see
        // form_set_cache()
    }

    $statement = db_select('cache_form','cf');
    $statement-&gt;fields( 'cf', array('expire') );
    $statement-&gt;condition('cid', $form_state_cid);

    $navigated = isset($form_state['input']['navigated']);

    if ( $statement-&gt;execute()-&gt;fetchAssoc() === FALSE &amp;&amp; $navigated ) {
        throw new Exception("The state-information for this form has expired.");
        // ^ I just place an exception here because recovery-actions for this
        // case are going to be system-dependent. If you know what those are for
        // your situation, they'd go here instead of this `throw` statement.
    }

} // my_module_submit_safety() OUT


Above, we use $form_state['input'] rather than $form_state['values'] since the latter will not include the results of the hidden field sent from the client's stale page in the case that $form_state information has been deleted. The strange dance of appending elements from a '#submit' step is done so that we don't run aground of the fact that my_module_form() is actually invoked twice (once immediately before '#submit' functions are called, and once after, each time with different values).

To test whether it works:


Load the form.
Navigate once.
Do: mysql -u &lt;userName&gt; -D &lt;databaseName&gt; [-p&lt;password&gt;] -e\
"DELETE FROM &lt;prefix&gt;_cache_form";.
Navigate again. You should see the message appear after this step.




Note: for security purposes, one might actually want to encrypt the hidden field's value (salting, timestamping, and including it no matter what), then reject the form outright if the value is found to be missing or adulterated in some way.