In my own experience as a GM -- I explored this from ECL 4-7 (With two side explorations to a cave system that flooded and drained with each passing of the tide, and one vaunt to the plane of water).
I did not venture into this realm until most of the party pinged to four. ECL 5 is when almost every full caster gets Water Breathing -- and Druids get Wildshape. For a low optimized party? That is when they can most likely start without DM fiat aid -- but with some real challenges remaining. Finding places to rest, what to do if Dispelled, and just good underwater movement is still a challenge (Looking at the full orc fighter with full plate, in my example).
By ECL 7 the party had crafted items, or adjusted their tactics, to the environment. Their were dungeons on islands between it all, but the novelty and challenge wore off. For the characters that could, movement and water breathing become trivial. For those that didn't? Extra dimensional spaces kicked in by then.
That is my own experience. But I didn't do anything really clever with the concept.