In the end I found that if I deleted my Search Results index and started from scratch, the search then worked however; this is the error message I get on some of the clicked on search result queries.
Server Error in '/' Application.
The resource cannot be found.
Description: HTTP 404. The resource you are looking for (or one of its dependencies) could have been removed, had its name changed, or is temporarily unavailable. Please review the following URL and make sure that it is spelled correctly.
I am thinking that maybe these results have been cached somewhere and the re-indexing has not flushed out past results? Could this be a possibility?
Is there a way to ensure that anything indexed is completely cleaned out when I re-index all the content again?