diff -urN a/install3/misc.c b/install3/misc.c
--- a/install3/misc.c	2009-11-22 01:39:59.000000000 +0100
+++ b/install3/misc.c	2009-11-22 01:35:25.795536883 +0100
@@ -319,7 +319,7 @@
     for (i=0; i < n_array_size(candidates); i++) {
         struct pkg *cand = n_array_nth(candidates, i);
 
-        if (pkg_is_colored_like(cand, marker)) {
+        if (!pkg_isset_mf(ictx->processed, cand, PKGMARK_BLACK) && pkg_is_colored_like(cand, marker)) {
             if (tmp == NULL)
                 tmp = n_array_clone(candidates);
             
@@ -354,7 +354,7 @@
                 struct pkg **best_pkg, tn_array *candidates)
 {
     tn_array *suspkgs = NULL, *tmpkgs;
-    int found = 0;
+    int found = 0, i;
 
     *best_pkg = NULL;
     found = pkgset_find_match_packages(ictx->ps, pkg, req, &suspkgs, 1);//ictx->strict);
@@ -391,6 +391,16 @@
 
     //trace(indent, "after removed rmmarked -> %d package(s)",
     //      n_array_size(suspkgs));
+
+    /* remove marked as BLACK from suspected packages, they have broken deps */
+    for (i = 0; i < n_array_size(suspkgs); i++) {
+	struct pkg *suspkg = n_array_nth(suspkgs, i);
+	
+	if (pkg_isset_mf(ictx->processed, suspkg, PKGMARK_BLACK)) {
+	    trace(indent, "- marked as BLACK %s", pkg_id(suspkg));
+	    n_array_remove_nth(suspkgs, i--);
+	}
+    }
         
     if (n_array_size(suspkgs) == 0) {
         found = 0;
diff -urN a/install3/process.c b/install3/process.c
--- a/install3/process.c	2009-11-22 01:39:38.000000000 +0100
+++ b/install3/process.c	2009-11-22 19:41:42.862076125 +0100
@@ -77,6 +77,11 @@
             i3_forget_error(ictx, pkg);
         }
     }
+
+    /* this package may be used again and we have to process it (do not
+     * stop on the first condition in i3_process_package()) to generate
+     * new ->obsoletedby as we removed them here. */    
+    pkg_clr_mf(ictx->processed, i3pkg->pkg, PKGMARK_GRAY);
     
     if (i3pkg->markedby) {
         indent = inc_indent(indent);