Analog input weirdness (barrel connector vs USB power)
Looking at the schematic the barrel plug has a couple of linear voltage regulators (top left of schematic), while the USB input just has a couple of MOSFETs (bottom right of schematic) which are basically just there to switch off the USB power if there is something plugged into the barrel jack (and also maybe provide a little input protection). So the Arduino is relying on the USB power to be pre-regulated. For the most part this is correct, but USB voltage can vary widely depending on the cable length (voltage drop), the power source it is connected to (no two computers or wall warts are the same), and how many devices are the same hub (if connected to a computer or hub). I would not rely on the two power sources being matched at all.

The flicker you are talking about sounds like the power coming from USB could have significant ripple. I doubt that the USB power is allowing you to "oversample". The way ADCs in AVRs work is they have a reference voltage and when sampling, will give you a reading of where the voltage is between 0 and the voltage reference. With a 10-bit ADC there are ~1000 steps, so to measure 100uV changes, you would have to have a 100 mV reference voltage, which according to the datasheet (p.379), the minimum is 1.0 V. Basically, it is physically impossible for the Arduino Mega to measure those kinds of changes.

What is more likely to be happening is that you are probably getting some weird aliasing between the ripple frequency of your USB voltage and the sampling frequency of your code. The best way to debug this kind of thing would be to pull out an oscilloscope and check if and how much ripple is coming off the USB power.

If accuracy is important to your project, and being able to accept both power inputs is a requirement, you might look into maybe getting your own external voltage reference and piping it into VREF. Otherwise, I would stick to only using the barrel plug as it is regulated and will be consistent.