Try going through old DomII maps. Illwinter's site here:
www.illwinter.com/dom2/maps.html would be a good place to start, but the DomII mods&maps forum has many more maps. The Illwinter site offers preview images of multiple maps, though. It has multiple maps fitting your province requirements: Three Necks, Albatha, Yalun-to and Cirlani, and there are several more at 100 or slightly more provinces.
Mapediting changed only little from DomII, so there might be some problems. About the only thing that can break the maps is the lack of command for disabling underwater nations. Some maps (NW Middle-Earth) crash if you choose random nations and get underwater race (or two, I'm not quite sure any more). If you find anything you feel is especially good, remember to mention it in here as well.