Posts not showing in search

I’m using WordPress posts to display tours for a travel company. Each post is a tour. Tours are categorized by country (e.g. “Britain” or “England”) so that a search of that category turns up scheduled tours.

A number of these tours were originally added with a post “published on” date that matched the (actual) future date of the tour (e.g. September 1, 2014). After it was discovered that these posts defaulted to “scheduled” rather than “published” (and weren’t available to searches) the publish dates were adjusted to earlier dates (e.g. August 22 2013), which solved that issue.

Some of these tours are still not showing in specific category searches. I have tours that return in a “England” search, but not a “Britain” (when those tours are categorized under each). I have checked, double-checked and triple-checked the checked categories and the publish date for each. I have even created duplicate listings and played with the date stamp to see if I could get a return for a “Britain” search.

Any ideas? Is there a cache or something I should be clearing?