Lo que también he visto es que sin siquiera tener programa las salidas del relé se me activan al meter tensión al arduino, durante un minimo instante, pero es algo que me mosquea... eso lo he visto alimentandolo tanto con la fuente de alimentación de 9V al jack de alimentación y con el cargador de movil USB a 5V.
Esto es algo que no debe preocuparte. Si el Arduino no tiene programa que importa que hace? Hace lo que ocurre cuando un micro sin programa propone en cada pin.
No tienes control sobre esta situación.
Si tienes controlo sobre un arduino programado.
Si crees que la solución es tener un capacitor, entonces coloca un capacitor de 470 a 1000 uF x tensión mayor a 5V entre 5V y GND y tendras entonces una especie de backup que demorará el apagado.
Prueba a ver.