Yeah--that's the problem, isn't it? That's basically what Linus was saying to those people who advised him to do a patent search on all of his code (or all of the code that goes into the kernel).
Yep. That's precisely why I'm not in favor of doing patent searches when you're developing a product or service. Granted, you could have tremendous liability if you're eventually found to have infringed; however, I'd argue that a patent search wouldn't be comprehensive enough to eliminate the possibility of somebody making a claim against you. I've seen some incredibly wacky patent infringement claims -- some of which were originally based on physical mechanical processes and the patent owner attempted to apply them to software. Odds are, a software patent owner wouldn't have thought of the threat of such a claim -- but it still happens. Likewise, it's also possible that a developer could become tained by the knowledge obtained while doing patent searches -- which introduces the possibility of a willful infringement claim. So the moral of the story remains ... don't do patent searches without very, very good reasons.