So many questions...where should i start...well, the "too many textures"-thing is a porting error from desktop jPCT. I've ported the documentation but not the functionality. I'll fix this.
About removing and unloading and adding them again...actually, this shouldn't be needed at all. The TextureManager will keep track of texture usage. There's no need to remove and add them all the time. What might be needed is to unload them, because if not, old and new texture might exist both for one frame and if you are low on memory, this might cause problems. However, by default unloading happens in the next frame, which might not be what you want in this situation. You can set Config.unloadImmediately=true to avoid this, but make sure that you call the unload method in your render thread then.
Other options that you might want to consider are setting Texture.defaultTo4bpp(true) and calling compress() on each larger texture.
VBOs will increase memory usage a little bit, but it shouldn't really matter. If you are using the latest alpha (that one with ES 2.0 support), they are enabled by default anyway.
The message in MemoryHelper refers to the memory that the VM has reserved ATM.
Edit: Actually, there's no need to dispose the World either as long as you don't plan to reload everything from scratch. In AlienRunner, all i do is a FrameBuffer.freeMemory() and i never saw any memory leak.