As Nuno has suggested, it should be related to the Cache.
Check (along with Cache Channel Service as suggested by Nuno), if you are using some custom caching in the your back-end (server side cache). If it is there, ensure there is mechanism to "Invalidate" the cache.
To confirm if it is related to the cache you may try updating and publishing and post that restart the COM+ and IIS app pool for your SDL Tridion Content Manager and check after clearing you browser cache. If the issue is no more there, then surely this is related to the Cache - If the caching is enabled with Cache Channel Service - Follow the suggestions as mentioned by Nuno and if it is Custom Logic for managing Cache - endure you also build a Cache Invalidation logic.
