@EA_JokerI managed to fix it myself by trick or treating Origin. With Origin closed, I started Battlelog straight from the browser. I logged in in BF4 and then switched to BF3. Then I found a server that runs "Gulf of Oman". I connected to that server, it asked to start Origin automatically. After Origin started it connected with no "Back to Karakand" DLC issue. Now I can connect normally from Origin every time. A friend of mine with the same issue, managed to fix it the same way.
But from the moment I fixed this, I am facing another issue (my friend however does not). Origin shows BF3 as new game and I have lost some unlocked weapons. EA Advisor have not managed to help with this either... They urged me to uninstall - install, repair, update the game, clear Origin cashes and some other stuff that did nothing. It looks it is an account based problem since in Battlelog everything is in place but when I start the game, my weapons are not there. So it is not a server based problem. It is not client based either, because I played the game in another friends computer and the same issue occurs. Also when I try to connect to some severs it throws me a message that I am missing content.