A possible mechanism
As promised, here is my take on the problem.
Suppose we have two fluids A and B, with densities D1 and D2 respecitvely. D1 < D2. For the moment, let's assume we have less of fluid A. For a column of fluid B of heigt h, the weight of the column is w = D2*h*g, where g is the graviational acceleration, and assumming a negligible variation in Di and g. For a column of fluid of the same height, where a fraction f of that height is fluid A (and the rest is fluid B), the weight would be w' = f*D1*h*g + (1-f)*D2*h*g. Obviously, since D1 < D2, we get that w' < w. The same applies if Di and g do vary significantly, except that the weight formulas would be more complex.
Now, let's see what happens near a bubble of fluid A, immersed in fluid B. Let's look at some depth h, which is slightly deeper than the bottom edge of the bubble. Every spot that is under the bubble, is under a column of fluid that weights w'. Every other spot is under a column that weights w. The weight of a column of fluid causes the fluid under that column to compress a little (even if the fluid is an "incompressible" liquid). From a molecular point of view, the heavier the column of fluid, the harder the molucules need to push in order to "hold it up". But they can only push so hard. So the column pushes them down, until they are sufficiently close to nearby molecules for the electrostatic repulsion beween them to be strong enough to hold the column up. Once the fluid under a column has been compressed, the compression results in a higher hydrostatical pressure. In other words, the motion of the molecules distributes the downward force of the column in all directions. But since w' < w, the resulting pressure under the bubble is lower than the surrounding pressure. So the surrounding molecules will move under the bubble, strivng to equalize the pressure. In doing so, they will raise the pressure under the bubble such that it is more than it should be according to w'. In other words, the pressure under the bubble will rise enough to overcome the weight of the fluid above that area. As a result, all the columns of fluid that contain fluid A, will be pusshed upwards. And since fluid flows downhill, some of the fluid in those columns will flow sidewards to reduce the column's height as necessary. All that happens simultaneouly and continuously until the bubble can rise no further.
If we have a bubble of fluid B inside fluid A, it will sink by a similar process - the pressure under the bubble will initially be higher then the surrounding pressure; it will be reduced, and will no longer be capable of holding the bubble up. If we have equal amounts of the fluids, then both processes will occur.
I'm not sure how this accounts for the apparent higher bouyancy at larger depths, but then I'm not entirely sure how this works macroscopically either, or whether this effect even applies to the cases of fluid in fluid (i.e. when the immersed "object's" volume is not necessarily constant)...
Intermixing:
Often, the two fluids can intermix, and desolve in one another. As long the solubility limit is not reached, the fluids will desolve in one another. This means that the molecules of the desolved fluid will be separated from the other molecules of that fluid. As a consequence, one cannot talk about the density of the desolved fluid (since you need multiple molecules to define density), and so bouyancy will not occur. Once the solubility limit is reached, bubbles will start to form, and then the above analysis can be applied to those bubbles. If there are no impurities that would allow bubbles to nucleate, we would get a supersaturated solution, and again no bouyancy would occur. This suggests that if the mutual solubility is perfect (100% solubility), and the two fluids have been thouroughly mixed, neither fluid will experience bouyancy. In addition, the easier the two fluids intermix, the less well defined the borders of the bubbles would be, if they do form.
Any comments are welcome.