Go for a more subtle approach to isearch-fail.

Use a red strike-through rather than full-on red backgrounds.