But why then does it work when I've got both the USB and the external power source?
How does my USB influence (/filter) this noise?
The on board auto-voltage selector circuit will switch to USB power if both power sources (USB & external) are available, so the only test for the external power quality is when only it is available. I suspect that the external power module is a poor quality unit that has a whole lot of ripple voltage. You might want to try a better power module, or perhaps try a 12vdc battery to see if the problem goes away. A proper quality power module should not require adding additional filtering and bypass capacitors, but adding such would probably fix what you are seeing.
Another possiblity is the warning from the site you posted: cap-sensors
Grounding and other known issues
The grounding of the 'duino board is very important in capacitive sensing. The board needs to have some connection to ground, even if this is not a low-impedance path such as a wire attached to a water pipe.
Capacitive sensing has some quirks with laptops unconnected to mains power. The laptop itself tends to become sensitive and bringing a hand near the laptop will change the returned values.
Connecting the charging cord to the laptop will usually be enough to get things working correctly. Connecting the arduino ground to an earth ground (e.g.water pipe) could be another solution.
Another solution that seems to have worked well on at least one installation, is to run a foil ground plane under the sensor foil (insulated by plastic, paper etc), and connected by a wire to ground. This worked really well to stabilize sensor values and also seemed to dramatically increase sensor sensitivity.
It's possible that your USB power is properly grounded to your PC's AC outlet, where your external power module will not have a hardwired ground connection to the AC power system. You might want to try some of their suggestions.