controlling which project header file Xcode will include

The key part of the answer is to use USE_HEADERMAP = NO as suggested by Chris in a comment. Here are the details.

Short recipe (checked in Xcode 3.2.2):

1. add a custom build setting of USE_HEADERMAP = NO for each concerned target. Here is how:
   1.1. Open the target’s info panel on the “Build” pane.
   1.2. Pull down the action pop-up menu at the bottom left of the window, select “Add User-Defined Setting”.
   1.3. In the newly added line, set the first column (“Setting”) to USE_HEADERMAP, and the second column (“Value”) to NO.

2. add the correct include path to each target (target Build settings “Header Search Paths”). In my example that would be:
   2.1. add TheirOldLib for “old” target
   2.2. add TheirNewLib for “new” target

Step 1 disables the automatic header map feature of Xcode, through which any header file included in the project is directly accessible through its name, whatever its actual path. When two headers have the same name, this feature leads to an unresolvable ambiguity.

Step 2 allows for the #include "theirLib.h" to work without qualifying the header file actual path name.

These two steps together fulfill my two constraints.

Finally, USE_HEADERMAP is not documented by Apple, as far as I can tell. I’ll fill a bug report for that, as this setting is crucial in a number of cases, as googling for it reveals. Reported as rdar://7840694. Also on open Radar as http://openradar.appspot.com/radar?id=253401