Only reasonable answer is those people are indeed viewing a 'cached' version.
If you are using ANY cache/speed-optimize plugin, disable it, verify if problem is fixed. If it is fixed, all you need to do is uninstall that plugin and use some other instead. I use W3 total cache without such problems, note there is a SETTING in the cache plugin to treat LOGGED IN members in a different way, never serve cache for them.
In case uninstalling cache plugin did not help, see via FTP if there are files/folders of an old cache plugin remaining. If you spot folders named "cache" thats suspicious. Maybe a poorly written plugin installed in the past, and never uninstalled properly, left entries in database too...
Last, you may want to take a look at your domain .htaccess file. Download it with FTP, open it in text editor, there should be only a few lines in there, the default wordpress entry. If any OTHER entries found, please post here so we can take a look.
* Disabling the fancy seo permalinks, should leave you with an empty .htaccess file. Try disable permalinks for a while , see if this solves the problem.
Last, but not least:
Visitors reporting this problem, are accessing via proxy, and they probably dont even know it. Maybe their ISP (internet PROVIDER company) is using this technique of serving to clients cached pages! In some countries, this happens ...a lot :)