This is because every ISP in the world takes their time to update their DNS cache reflecting any and all domain name DNS changes. Some update pretty quick, others take a while.
You say 50% of the time it pulls up the old server. It's possible your ISP's refreshing their DNS, but it "fluctuates" between the old and the new in the midst of "cleaning house".
Assuming the registrar confirms the domain's using the right pair or so of DNS, and all independent DNS troubleshooting tools show the right settings, your last stop will be your ISP.
Of course, other factors could come into play like routers, TTL, etc.
Anyway, you say it's a country code top level domain (ccTLD) and it's using the right DNS. I would've said check with your hosting provider, but your first post said your site pulls up the old and new one 50% each of the time.
In my mind, it's your Internet Service Provider (ISP) you gotta talk to. Chances are they're cleaning up their data whenever they refresh their machines assigned to "cache" or memorize the DNS data of domain names.
Make sure your browser's clean as well. ;)
Note that I am talking about a change in DNS records (such as when moving a website), NOT a change of registered DNS servers. It sounds, though, like this is a simple case of a changed DNS record.
There is a number associated with each DNS record called TTL, or time-to-live. Whenever a record is loaded, the server or resolver that loaded it also gets the TTL value. (A "resolver" is what's built into your operating system. A caching server - usually at your ISP - is where your resolver generally gets it's DNS data from.
A typical value for TTL might be 86,400, or one day. (TTL values are in seconds.) After a server or resolver has had the record for 86,400 seconds, it is supposed to remove it's cache of the record. Any new requests for the record after the cache has expired require a new request to an authorative server. (i.e. one of YOUR DNS servers.)
If you know in advance that you can going to change a DNS record, you can reduce the TTL to a small value - perhaps, say, 5 minutes, or 300. Then, wait for the old TTL value to expire - that is, in the example give, wait 24 hours. Now, make yor change. Wait another 5 minutes, and then you can increase the TTL back to 86,400.
In theory, at this point, EVERYBODY should be getting the new server. Certainly 99+% should be getting the new server.
Don't guess that a DNS change will take 1-3 days. Find out what your TTL is, and KNOW how long it will take. And then TAKE CONTROL of it, and avoid this problem altogether.
Note that some DNS providers will not allow you to reduce your TTL to as low as 300. However, most good for-pay services will let you do this, as it is an essential tool when switching servers to a different hosting provider.
Now, if you switched your registered DNS servers, then this is a different problem. That has to be done at the registrar, and then the registrar has to send an update to the root servers. The update to the root servers can take a variable time, depending on the registry. You do NOT have to change your registered DNS servers to change web hosting providers. In fact, I'd recommend against having your web hosting company also host your DNS, for any of a number of reasons, including the inability to control the timing of updates.