search from modify html output
I wanted to do the same thing and after struggling with all kind of hooks/theme functions, I finally found a solution directly inspired from bootstrap.

Here the 2 links of bootstrap implementation:


bootstrap_form_alter 
bootstrap theme function


And for my purpose, I've created a custom module to implement a custom search block. 
So in MYMODULE.module file, I've put:

/**
 * Implements hook_theme()
 */
function MYMODULE_theme() {
  return array(
    'MYMODULE_search_form_wrapper' =&gt; array(
      'render element'  =&gt; 'element',
    ),
  );
}

/**
 * Implements hook_form_alter()
 */
function MYMODULE_form_alter(&amp;$form, &amp;$form_state, $form_id) {
  if ($form_id == 'search_block_form') {
    //other implementations in themes/MY-THEME/template.php
    $form['actions']['submit']['#attributes']['class'][] = 'element-invisible';
    $form['search_block_form']['#theme_wrappers'] = array('MYMODULE_search_form_wrapper');
  }
}

function theme_MYMODULE_search_form_wrapper($variables) {

  $output = $variables['element']['#children'];
  $output .= '&lt;button type="submit" class="btn-foldingsearch"&gt;';
  $output .= t('Search');
  $output .= '&lt;/button&gt;';
  $output .= '&lt;span class="icon-search icon-foldingsearch rotated"&gt;&lt;/span&gt;';

  return $output;
}


Anyway, you'll have to adapt it to your configuration. Hope it helps.