If you have any sort of reverse proxy caching, you need to make sure that is cleared as well as your Magento cache.
If you have a server cluster setup, make sure that your cache is mounted to share across these clusters.
What does your local.xml look like? Do you have a <cache>
node set in there? If so, the <backend>
and <slow_backend>
nodes could be overriding the default behaviors for your caching.
Try this: Turn off your caching entirely, (disable it in the backend). Do your changes show up now? If so, it could be a caching behavior problem set by these particular nodes.