New web design/structure and Google Site search

I have a client that uses a simple javascript code to allow visitors to search their website using Google. I’ve recently redesigned their website and it appears there are some old pages that are cached in google that should disappear but are still showing.

Using this link, the first search result is correct. But every result after that ends in the old “search.asp” format and Google is still caching this old search page:
http://www.newhair.com/search.html?Q=steve+hartman&b.x=0&b.y=0

Whats the best approach to handle this? I’ve already re-submitted the website URL to Google to get it to re-index the website, but I’m not sure if I should also do a 301 redirect as well.

Whenever you change any public URL on a website, it’s always worth a good idea to put a 301 redirect on there, to the best match page in the new structure (not just redirecting everything to the home page). You never know who is linking or bookmarking those pages, not to mention search engines. If those old pages are still being returned 200 A-OK, Google will keep them in its index, and won’t know there’s anything wrong with them.