I think I finally found an answer on how to properly reset the modem in case it just won't attach to a network.
Reset the modem by sending following AT-command:
lte.send_at_cmd('AT+SQNSFACTORYRESET=?')
Unlike lte.factory_reset() - which seems to use AT-command AT+SQNSFACTORYRESET - this command will successfully reset the modem to factory state.
A reboot of the device is necessary to finalize the reset!
After this process the modem should attach to the network without any issues!
Also, for further information see: AT Commands Reference Manual, 15.1 Device Reset to Factory State