I'll mention once more that this seems to be a situation where it may be well worth it for the poster to employ an experienced travel agent. I've benefited from having one such TA book corporate travel, and have been continually amazed at his ability to find optimal ways of achieving complex itineraries at excellent cost. The combination of less-than wizard-class traveler, multiple people in the party, complex itinerary, and good number of variables, makes this sound like a situation where expert human assistance can be invaluable.