> Especially because an air bubble should reduce in volume due to the surrounding pressure, and therefore reduce its buoyancy (I think).

Yup. In fact, given that a lot of materials are more compressible than water, most things become less bouyant the deeper you go exactly because the water pressure compresses them. Objects that float on top of water can, at a sufficient depth, be compressed to the density of the water around them and begin to sink instead of floating!