For a dark background, I think we should use the maximal saturation, and
pick a color on the lightness-darkness axis.  The complement for #ff8888
on this axis is "red4" which is dark enough.  I checked that it looks good
on a dark background:

Index: lisp/isearch.el
===================================================================
RCS file: /sources/emacs/emacs/lisp/isearch.el,v
retrieving revision 1.310
diff -c -r1.310 isearch.el
*** lisp/isearch.el	12 Feb 2008 00:50:44 -0000	1.310
--- lisp/isearch.el	24 Feb 2008 17:30:47 -0000
***************
*** 231,238 ****
    :group 'basic-faces)
  (defvar isearch 'isearch)
  
! (defface isearch-fail '((t (:foreground "Black" :background "Plum")))
    "Face for highlighting failed part in Isearch echo-area message."
    :group 'isearch)
  
  (defcustom isearch-lazy-highlight t
--- 231,250 ----
    :group 'basic-faces)
  (defvar isearch 'isearch)
  
! (defface isearch-fail
!   '((((class color) (min-colors 88) (background light))
!      (:background "#ff8888"))
!     (((class color) (min-colors 88) (background dark))
!      (:background "red4"))
!     (((class color) (min-colors 16))
!      (:background "red"))
!     (((class color) (min-colors 8))
!      (:background "red"))
!     (((class color grayscale))
!      :foreground "grey")
!     (t (:inverse-video t)))
    "Face for highlighting failed part in Isearch echo-area message."
+   :version "23.1"
    :group 'isearch)
  
  (defcustom isearch-lazy-highlight t

-- 
Juri Linkov
http://www.jurta.org/emacs/