I was thinking this for awhile, with 1/3 of the provinces already being used, (Skyrim, Morrowind, and Cyrodiil)
I was trying to think which province would be the best to go to next, and so thought Valenwood would be cool with the stories of it's nature and Migratory tree villages. I looked at the map however, and Valenwood is one of the smallest provinces, but right next to it is Elsweyr, which has had an interesting history with Valenwood, and is just as big. Put them together, and they're around the size of Skyrim, and with their history and different terrains I thought it would be a cool idea. The story could possibly involve learning whether or not the Thalmor really did bring back Masser and Secunda, which made Elsweyr join the Dominon. I thought it would be a pretty nice idea and was wondering what you guys thought.
It'd be annoying to constantly chase down a city every time you had to return to it.
Then you have to consider how would you make the animations for a moving tree. Would they make the roots look like spider legs and have it move like that?
Finally, there are the console limitations that might make it difficult for that many trees to move without causing some issues.
The caravans are, at most, 4 NPC that have tents that just spawn out of nowhere which makes it easier to implement but to move an entire city with all the NPCs, quests, etc not being effected seems highly problematic.
I think LOTRO, when it first came out, actually had moving trees. In the Old Forest, they actually made the paths through the forest change at night. It usually happened off screen so you weren't aware of it and couldn't see it, but suddenly, the way to the exit was no longer there and you were always pushed down toward the spider den to the south.
Something similar could be done for Falinesti. It could move when the time changes or when you leave the area's cells. This would give the impression that it's moving, but so slowly you can't observe it. If you enter a building and zone into an "instance", when you come back out, the tree will have moved.
They probably could make it work like that but I can't help but feel there might be some issues with it, more specifically with quests involving Falinesti. This is Bethesda after all and their games are horribly glitchy, so adding a moving city just seems like a huge problem waiting to happen.