Well you could always capture someone else's underwater fortress
Seriously though, there is n4w1 spell in conj 7 that lets you summon an underwater castle for 50 nature gems. It still needs to be cast underwater though.
Finding fortresses is also a lot more common underwater, search with nature mages.