You created a page with the slug search to “capture” that URL, but WordPress by default already uses that URL for search results. So you were “lucky” that this worked for you, and this is the reason the redirect supermethod mentioned will work.
So, instead of creating a “fake” page to hold the template, you should just rename the template to search.php, like tnorthcutt suggested. If you still want to have content from the page defined in the admin area, I suggest you rename this page and get it via get_posts() or another method, because the main loop will contain search results, not this specific page.