Ok, so I went to my local Orange Shop, have them reset my account, change my SIM card, payed my bill (to exclude every possibility that it could be a network issue
). Aaaaaaaaand.. it was still not connecting to network. Went to a "pro" guy to have it reflashed. Same problem.
After thinking to smash it into a wall, turn acid on it and put it on fire, I've decided to play around with phone's settings (though it made no sense since I've reflashed it a few dozen times, each time with different rom, so settings would be reset).
So I've deactivated the PIN request on start-up. Aaaaaaaand.. it works! It connects to network, to internet, to everything. If I switch the PIN request back on, it doesn't work.
So it works without PIN request, doesn't with PIN request. What in the name of Chewbacca is happening?