The reason it isn’t working is because you haven’t told WordPress how to handle that page. You can do so by applying a rewrite rule in the following manner.
add_action( 'init', 'wpse_63716_search_rule' );
function wpse_63716_search_rule(){
add_rewrite_rule('^suche/([^/]*)?', 'index.php?s=$matches[1]', 'top');
}
Don’t forget to flush the permalinks after adding the above code.