Sounds like a issue with browser cache or a broken proxy (nginx for example).
Perhaps your site tells the browser to cache things too long. This site has a lot of rules for browser cache for example.
Take a look at your .htaccess file to see what’s going on there with browser cache.
In the case of proxies, you’d have to have your hosting company take a look at that.