Index: pym/portage/__init__.py
===================================================================
--- pym/portage/__init__.py	(revision 12023)
+++ pym/portage/__init__.py	(revision 12024)
@@ -6385,6 +6385,8 @@
 		all_available = True
 		versions = {}
 		for atom in atoms:
+			if atom[:1] == "!":
+				continue
 			avail_pkg = mydbapi.match(atom)
 			if avail_pkg:
 				avail_pkg = avail_pkg[-1] # highest (ascending order)
@@ -6402,7 +6404,8 @@
 			# If any version of a package is installed then we assume that it
 			# is preferred over other possible packages choices.
 			all_installed = True
-			for atom in set([dep_getkey(atom) for atom in atoms]):
+			for atom in set([dep_getkey(atom) for atom in atoms \
+				if atom[:1] != "!"]):
 				# New-style virtuals have zero cost to install.
 				if not vardb.match(atom) and not atom.startswith("virtual/"):
 					all_installed = False