Dear BurkeKnight, thanks once again for a great tip to call for help at my hosting company. The girl there was really of a great help (although the problem was not in the hosting or server). The problem was in 2 plugins: Login Ninja and Instant Search & Suggest. I deactivated all plugins and then started activating them one by one, this is how I found which ones are mal-functioning. Perhaps this tip will be useful for some of you experiencing the same problem.
