From memory, I vaguely remember there was an issue with parameter not updating on the server, a long time ago. I hope Tableau has fixed that by now, but what version server are you running?
Generally speaking, I often observe cases when I re-publish something, but a user who looked at the view some time before than does not see changes when they close and re-open the view. Sometimes all it takes to fix this is to click the "Refresh Data" button at the top centre of the view. But at least once we had to reboot the server machine to shake this mysterious cashing off.
From you description, you are doing everything right and it looks like one of those overzealous caching by Tableau Server.
Users are connecting to the published data source on the Tableau Server from within the Tableau Desktop app. No web access is involved.
We're running Tableau 7 at this point. Refreshing the data doesn't seem to help.