I was ruling out all the other losses, because even if the theoretical net compression losses perfectly equal the theoretical ascent gains, then it is *mathematically* proven to be a stupid idea. (yes, slow assumed under water, ignore the drag for now too. With a direct coupling via a tether the speed doesn't really matter, just force and distance).
I'm no Archimedes though. Apparently the compressiblity of air is a factor too, a ballon will be more buoyant on the ground, but a barrel in the water isn't more buoyant at depth, just a function of displacement...
http://www.physicsforums.com/showthread.php?t=322544