How can I modify the advanced search form when my hook runs too early?
Changing the module weight will work, but sometimes that can cause problems with the order in which other hooks in your module are invoked.
Drupal provides hook_module_implements_alter() for exactly this sort of situation, so that you can target the order a specific hook is run in:

Alter the registry of modules implementing a hook.
This hook is invoked during module_implements(). A module may implement this hook in order to reorder the implementing modules, which are otherwise ordered by the module's system weight.

The code might look something like
function MYMODULE_module_implements_alter(&amp;$implementations, $hook) {
  if ($hook == 'form_alter') {
    // Move MYMODULE to the end of the list.
    $group = $implementations['MYMODULE'];
    unset($implementations['MYMODULE']);
    $implementations['MYMODULE'] = $group;
  }
}

Once you clear the cache your module's implementation of hook_form_alter() will be invoked last (unless of course another module is implementing hook_module_implements_alter() and altering the order again. But that's a different story).
I personally prefer this method as it's just a simple code change, no need to maintain any changes to the system table in the database.
I'm not sure how well that works with a form_FORM_ID_alter hook (never tried it), but with this method you can at least make sure that only the weight for hook_form_alter() need be updated.
Actually looking at the code for drupal_alter(), changing the conditional to if ($hook == 'form_search_form_alter') would probably work.