Where is $form_state stored between form build, and form submit functions? I assume that $form_state data can normally be stored either in the database, or in the session.

In this code:

function _module_name_main_form($form, $form_state) {
  $form_state['random_extra_data'] = some_func();
}

function _module_name_main_form_submit($form, $form_state) {
  $important_data = $form_state['random_extra_data'];
}


I trust that there are limits to how the user can manipulate $form_state, which isn't true if $form_state['random_extra_data'] is stored in the session.

Is that safe to do?
The cache_form table stores $form_state, so except for the values passed on by the client, which should be validated anyway, it is safe to trust the content in $form_state.