[Nexus 4 Q&A, Help & Troubleshooting] elsrss:
So, here is an update with a summary to what has happened with my Nexus 4 (which works well) and my wife's one (which has the SOD problem). I put this summary since the thread is long, maybe it helps to sum up things, at least for my case:

a) We bought two Nexus 4 on the same day from the same store (not Google Play), opened an account in the same cell provider.

b) My wife's phone had an SOD from day 1. Initially we thought it was some kind of restart due to updates on the new phone so we ignored it. But it kept happening every two -three days.

c) We brought the phone back to the store after 10 days, got a replacement for her

d) After two days, we get an SOD in the new phone. This keeps happening once per charge cycle at least, but not on regular intervals. Some times there were four days without SOD.

e) We noticed a step in the battery charge level after recovering the phone from an SOD. That is a common feature we notice in all SODs afterwards. Furthermore, the battery level was staying flat for hours after recovering from an SOD, which makes no sense, as sometimes my wife was using her phone to take pictures & make phone calls. These things use a lot of power.

f) We could not find a pattern on when this was happening, but in most cases (not always), this was occurring during the night (while the phone was on stand-by) or when my wife was connected to her workplace wireless network.

g) We called Google (few months ago) and they told us they were unaware of our problem. They suggested to do a phone recovery (can't remember how they instructed us to do that), and then if that didn't work, to do a factory reset. If none of these worked, they suggested us to contact LG (in Germany).

h) Well, nothing worked, but before contacting LG in Germany, we tried few things. Activated Daydream, installed an app called "Wake lock", deactivated bluetooth, deactivated NFC. The "wake lock" solution appeared to work for some time (the phone survived once a charge cycle without SOD), but that was the best we achieved. Eventually, SOD kept happening so we send the phone to LG.

i) It took two weeks for LG to respond. They did not send us a replacement, but a "fixed" phone claiming there was a software issue. That is strange since we had 4.2.2 on the phone, while many other phones with similar software have no problems. So, maybe it was a firmware issue or something not android related (not sure if that makes sense). LG didnt say anything more specific

j) Interestingly, there was no SOD for almost three weeks. There were 1-2 cases were my wife was prompted by the phone to put the SIM code, indicating a random reboot took place (never happened before).

k) Then, my wife travelled to another country 3 days ago for business. She noticed an SOD (+ the typical battery level step) few hours after connecting to the wireless network of the hotel and the local T-mobile cell provider. She also got 1-2 random reboots within the few days she is already there.

The last event tells me that the problem is definitely tied to the wireless or the sim-card and seems not to be a hardware issue. I guess, the problem will persist even if we get a replacement phone, because I get the impression that somehow the issue is "personalized", since it persisted in both phones my wife got (so much bad luck?). Not sure if it makes sense to wait for some software update by google or to get a different model for her...

For the record, the phone runs stock Android 4.2.2, problems were also there with 4.2.1.