Funny thing! I totally forgot to take care of this issue, used WiFi as little as possible to go around it. And all of a sudden, for three days now, the issue is gone!!
I didn't do anything unusual, it was not a PA update day, nothing special. But no wrong locations anymore...