arama formunu değiştirip,

<form method="get" id="searchform" onsubmit="aramaduzenle();" action="<?php bloginfo('home'); ?>">
	<input type="text" value="<?php the_search_query(); ?>" name="s" id="s" />
	<input type="submit" id="searchsubmit" value="Ara" />
</form>

yukarıdaki hale getirdim, yani onsubmit ekledim.

sonra headera onsubmite verdiğim fonksiyonu tanımladım:

<script type="text/javascript">
	function aramaduzenle(){
		var key = jQuery("#s").val();
		ykey = key.split(' ').join('-');
		jQuery("#s").val( ykey );
	}
</script>

sonra da aradım. arada - olarak çıktı tabi sonuç bulunamadı

burada da kalıcı bağlantı için bir çözüm var:
http://r3m1ck.us/other/change-search-permalink-2

arama sonucunuz: siteadi.com/search/aranan-kelime şeklinde oluyor.
belki burada bir htaccess düzenlemesi yaparak yanıt verebilirsiniz.