Ok, problem solved.
I took it out of the dash temporarily and it started seeing 10 satellites, after it locked in I put it back, the signal strength decreased a lot, but still it works, and continues to work after power-off/on.
So it works now, but I'll still move it on the dash, near the windshield.
Edit: It stopped working again, I really must move it over the dash. I still don't understand why it worked before and it doesn't work now. And why it doesn't find satellites but if I pull it out and it locks on, then it can continue to communicate with 7-8 satellites from inside the dash.