Hello everybody, I'd like to thank you all for participating in solving this puzzle - I finally got it nailed down, and I'm a bit sorry to end the thread in anticlimax, but here goes...
So, in post #37 I detailed all possible categories of reasons I could think of that could cause this behavior. But I forgot about one other category - measurement errors. What could go wrong with simple voltage measurement, you ask? Normally, not much, but when you measure millivolts, and circuit has few amps flowing through, its a different story. In short, I measured various voltages by treating everything connected to the same wire (disregarding the physical dimensions of wire) as the same point, as I usually do. But usually I don't deal with several amps of current, and when I do, typically don't care for voltages that are fractions of Volt in amplitude.
As mr. Murphy would predicted, it turns out that I measured the voltage at probably worst possible physical point - I connected multimeter + probe at the load itself (its a hefty resistor with a nice thick terminals), and kept it there (since +V is my reference point), while probing various potentials by moving negative probe around. So I was always measuring (not negligible) voltage drop along the wires and all the connections. To make things worse, the load was not very firmly fixed to the rest of the circuit, but enough to make a galvanic contact. The breadboard itself seems to have quite thin wire internally connecting the contacts. The combination of these factors conspired to produce up to 1V of voltage drop (so, it all added about 0.3-0.5 ohms overall resistance if current is 2-3 A). This is the reason that I got such a varying results - it was due to the physical point I chosen to pick for measurement, and not related to the various other solutions you proposed and I tried. The primary criteria for choosing the point of measurement was the ease of access (since the mosfet was getting hot fast, I wanted to complete the measurement as quickly as possible). The voltage drop along the wires and contacts due to the large current was the last thing on my mind, but there you go - live and learn...
Once I realized this, I reverted to the original solution (the before post #26) and measured the voltage difference directly at the pins of opamp inputs - the voltage was just a few millivolts, irrespective of the load I tried, exactly as you expected it should be.
Once again, I'm sorry for wasting everybody's time, but I'm glad that, with your help, I got it solved and learned quite a bit thanks to you, so thanks again!