Ok so I didnt have time to try it till today, what I found out is that it was indeed a problem with the hosting server. I contacted them and they made some changes in their settings.
I am no succesfully able to receive wordpress mail, for both hotmail and gmail.
Thanks for all the suggestions, it luckily only took me some contact with my hosting provider!
