It certainly sounds like a caching issue. Even if you disable W3 Total Cache, often it keeps cache code in your wp-config.php file and .htaccess. Purge all that code and see if the problem persists.
Also, make sure your web host does not have server caching. Many “managed” platforms have a built-in cache (eg. WP Engine, SiteGround) which can lead to unusual behaviour. Purge or switch off any server cache you find.
The other thing it could be is your permalinks. Go to the Permalinks page and just click “Save Changes” to force the permalink records in the database to be rebuilt. That should flush out any erroneous records.