I like the duffel bag idea that several people have suggested. On my trips that involve air travel, I clip my two panniers together, and carry it on board as a single item. I leave my tools attached to the seatpost and a small pack.
I have never had a problem with baggage handlers or customs officials doing this.