We ended up going with one of these (actually a SunLite bag for folding bikes - UDC’s comes with foam panels).
It fit the 29er fine, pedals and seatpost removed (but still in the bag). We did a 24 the same way; no issues checking them with Delta/Northwest.
I’m traveling with British Airways (yes, I read the horror story, but after I had booked the flight…) to Europe, and I am taking my 36" Coker. Does anybody have any experience or advice for what I need to do for the airline? Last time I flew with it, I just wrapped up the pedals and handlebars with bubble wrap and American Airlines took it, but the rules for British seem to be different.