Arduino not working when RE-powering up while connected to PC

I have a PC connected to the USB port on my Arduino-based control. Everything is fine when the PC is turned on and then the Arduino controller is turned on. However, when you shut down the Arduino controller and then restart it, the Arduino controller goes amuk. It is turning a light on which suggests it came out of setup, turned the light on and then went amuk, but I can’t be certain of this.
Here are some important facts. If I disconnect the USB connection to the PC before shutting down the Arduino controller, the Arduino controller restarts just fine. Then, when I reconnect the USB port, everything works fine. The Arduino controller has its own 9 vdc power supply plugged into Arduino and it shuts down when the controller is shut down.
This controller is being used in a business and I would rather eliminate this issue rather than impose the disconnect procedure that we know works. Also, is something going on that could cause other problems?

What is going on here and is there any fix?

I forgot to add that I am using the Mega 2560.

You did not say anything about what is connected to your project.

I can imaging this kind of behavior could happen when you power external components from the Arduino 5V rail, totally consuming about 500mA or a little bit more.

The 5V rail can easily supply more than 500 mA, up to 1000 mA, when powered by an external power supply. The USB power can only supply 500 mA and will shutdown if more current is consumed.

Just my guess.

I'm not using the Arduino power supply for all the external devices. I am using a separate 5 volt power supply.

I suspect the problem has something to do with switching back and forth between the Arduino receiving power from the PC through the USB connection and then receiving power from the separate 9 vdc supply when the control is turned on. It works the first time, but when you power up the controller/9 volt supply the second time, Arduino goes amuk. I'm not sure how the various interrupts might be involved here? I don't use interrupts and have done nothing in software to deal with problems that might exist when recovering from brown outs or power loss (or switching between power sources?).

Are you using the Serial library ?

If you have a line Serial.begin(9600) , (9600 or any other valid baudrate) in your sketch, even as part of debug code. Then it is normal that your program stops when you reconnect the USB cable.