I had the same idea, but instead of a flood, it would have been the Misty Lake becoming salty, and strange youkai appearing from it.
Stage 1 would be just above the lake.
Stage 2 would be a strange new cave.
Stage 3 would be a beautiful coral garden or what.
Stage 4 would be the bottom of the sea.
Stage 5 would be an underwater city.
Stage 6 would be a palace, the boss is the Ruler of the city, who explains that this underwater place and the few islands above water is another Gensokyo like place, but on the ocean. They just learned about Gensokyo and they wanted some connections.
Ex would be above the ocean, around the islands, and the Ex-boss would be the Barrier Maiden of this sealed world. Enter brown-skinned loli.