Relay switching issue between 2 sources

That's called "backfeeding" and occurs if there is ANY voltage on a digital or analog pin after disconnecting power from arduino +5V pin. The voltage comes through the ATmega328 internal protection diodes from the GPIO pins to the +5V .
The anode is on the GPIO pin (analog or digital) and the cathode of the diode is on +5V. What this means ( in plain English) is that you CANNOT turn ZOFF the arduino Power if there is ANY voltage on ANY analog or digital pin.