Are you using cocos2d v2? You probably have memory leaks since unused textures are removed when necessary. Try profiling your app to see if you have leaks and where they are at.
You also can call these methods yourself at the appropriate time, although I doubt you'd have to:
[[CCTextureCache sharedTextureCache] removeUnusedTextures];
[[CCSpriteFrameCache sharedSpriteFrameCache] removeUnusedSpriteFrames];
But again what you describe sounds more like memory leaks. When your application receives a memory warning the cached data is purged. During this purge the remove unused textures method is called on the texture cache, among other things. If you have 3/4 levels of data still lurking around long after you've exited those scenes, that sounds like a memory leak.
I'm assuming this only happens after visiting multiple scenes and the problem just isn't that your 4th scene is simply trying to load more data than the device can handle.