Ok... so there is another update to my previous problem.
It is not just a cache issue.
It actually does not correctly identify the domain when going without the "www".
So, "www.mydomain.com" will work fine but if you just have "http://mydomain.com", then it tries to use the first connection possible.