In initial testing I have left the default settings for the search extension and get the following results:

URL in address bar: www.example.com/search/gold?searchword=gold

This just redirects to the site home page and does not display any results. For the admin side see the attached image.

Open Manage Extensions page in JoomSEF and in Search extension parameters on the Common tab set "Ignore Itemids" option to "465" (without the quotes). Make sure to delete the search URLs using Manage SEF URLs page and clear cache. Does it help? If it doesn't, please post a screenshot again of newly created URLs.

Ok, some progress this time. The search page shows up showing the correct results spanned over 4 pages (20 per page). However clicking on the next page link sends us back to the home page of the site. The link for the next page of results is:

www.example.com/?start=20

That is obviously the problem, as there is nothing there to tell Joomla what it should be showing. Screengrab attached of the admin again. These are the URLs that work, although I did have to set "Handle search phrase as non-SEF" to yes to stop the first keyword being searched on from being a permanent fixture in the SEF URL.

Also worth noting is that once on the search results page you cannot use the form there to search on a new keyword. The form action is set to "/search/", entering a keyword, just goes to www.example.com/search and does not append any keyword info.

We've finally found a problem behind this. It will be fixed in next version of JoomSEF.
For now the Search component needs to have it's own Itemid for pagination to work properly, so you need to create a menu item for Search.