Since I always have a small backpack in addition to regular carry-on, I use this insert:
http://www.amazon.com/Crumpler-Haven.../dp/B0087B17E2 .
Because my DSLR is smaller than your 5DmII, I have the medium Haven. I think you would need the large.
All that said, since I added an Olympus OMD-EM5 kit to my camera collection, I haven't taken the DSLR on any air trips and haven't missed it. If you go with the Fuji or Sony ILC, I'll bet you make the same choice. Half the bulk and 1/3 the weight with little or no image quality loss is a strong argument.