A few thoughts:

1) I would tend to say it is too early to book, barring a great deal.

2) Is part of the issue a day of the week thing? I don't believe that AGP runs every day, so moving your outbound a day or so might fix your problem - assuming you can move your schedule to accomodate.

3) Are any of the segments you see on Orbitz or Expedia AF-coded flights? If so, I suspect that this is your problem. I know that Delta.com can mix and match DL and KL flights, but I don't think it can mix and match with AF flights for revenue tickets. I don't believe a multi-city search will solve this problem.

4) I've personally booked DL (and before the merger, NW) tickets on both Orbitz and Expedia without any problems at all. If I had to choose, I find that Orbitz has more robust flight search options, but wouldn't hesitate to buy from Expedia if they were cheaper.