If any expert will try same thing as I did then I hope he will add some comments here again.
Willen,
I accept your logic that if the amp works well with other supply then it is likely that the fault isn't with the amp.
If you look back at post #2 at my first advice to check that there is zero ohm between your audio output to the USB negative. I didn't see any clear comment from you that you did try that.
Let me elaborate: All the computers I've come across use common ground for all inputs and outputs. It is possible that some don't. If in your computer the ground isn't common then you can have strange problems because your link between the 2 ground points transfers the noise to the input. Some computers have current sense resistors on the common side of the output and that can cause your problem too. You wont notice this when you use the USB or headphones.
The easy way to check is with a DMM while your amp is unplugged. When I say zero ohm I mean not more than 0.1 ohm measured by a DMM.
If you find that the resistance is not zero you will have to add to your circuit an isolating audio transformer, the primary connected to the headphone output and the secondary to the input of your amp. You can try this solution even if you find zero resistance between the commons.
What that works against you the most is that you need a voltage gain of one and this amp gives you 40, it means that your signal to noise ratio is reduced by 40 if the noise comes from the supply.
Maybe audioguru can suggest a replacement amp with adjustable gain. You have to check what audioguru tells you; he is not a real guru and I think that he doesn't even have a beard and a big belly like a proper guru should have.