Removing the preferences file solves the problem. Does that mean that packages with negative Pin-Priorities get ignored by apt-cache search? If yes, is this docuemented somewhere? WM