Don't most of the airfare searching sites let you include your baggage situation into your query? Kayak does, at least. I just assumed the rest did as well.