Relay Sometimes Not Switching
I think the problem is with the way the relay is being powered. The voltage regulator on Arduino is not sufficient enough to provide the needed amperage for switching the relay properly and thus even if the led lights up the relay contacts are not touching with enough force. 

I would recommend you to use an external 5V source for powering the relay. Or if you are supplying your Arduino Nano with 5V then connect the relay's VCC to VIN of Arduino.

Also, do keep in mind that if the relay is not supplied with proper power, it can lead to internal sparking of switching contacts which can damage the relay.