I ASSUME that the power supply produces clean DC (but I don't really know nor can verify it).
Measure the voltage with a multimeter or oscilloscope, while connected to your Arduino. (e.g. measure VIN or right on the barrel jack.)
Can anyone exclude that it is an issue with initializing/accessing the USB port from the sketch while there is no USB port attached?
It is very unlikely this is the issue. Many of my projects send stuff to the serial port even when nothing is connected to it.
The behavior you describe sounds like the board is resetting. What is the total current are you drawing off of the 5V pin? Keep in mind that if the on-board regulator starts to over heat it will shut down (which can cause a reset.)