Are you sure you are powering at 3,9V? Measure it with a voltimeter when SIM800 is ON, i guess your batteries cannot mantain a steady 4,5V
I had one working for a month and suddenly it stops working. I was powering it with 4V but RX/TX lines were connected directly to 5V arduino ports.
I replaced by a spare one but this time add a level shiftter between arduino and RX to lower the signal to 2,8V. It is running now for 2 weeks without a fault.
For my experience, i advise:
1) Power SIM800 with a 4V LDO. Use a diode only if your input is very stable
2) Keep RX/TX lines below 2,8V
Can you please attach circuit diagram. I also experience such problems, Used one SIM800L for a month, then is stopped registering in the network, when I pull TX line from SIM800L, restart the module it registers in the network, then put TX back and it works, then if I reset the Arduino, it resets the SIM800L and can't register in the network again. Looks like problem is with module's serial ports, will test another one with voltage dividers...
Strange thing is no matter it's registered or no, it responds and communicates with Arduino OK, displays found networks, but when I send command to connect to the carrier AT+COPS=0,2,"40001" for example it responds ERROR....why?