Somebody may have already considered this, but Age of Kings and Age of Mythology allow you to take full map screen captures by hitting CNTRL+ALT+F12. I am not a practiced AOM map maker, but here is a thumbnail of a small test that I have been working on.
With AOM you can use the random map generator and then delete all objects of a given type that do not fit a Dom map quite easily. For this one, I created a blank one player map and just fiddled around with terrain and object placement, captured the map, opened the jpg in Gimp, scaled it to 1/4 and saved as tga. Now I need to replace white pixels and figure out how to make some easy borders that won't look to ugly. Somebody with a real knack for AOM map editing should be able to do some really awesome maps.
Previously I had looked at using Age of Wonders, but piecing all of the screen shots together is too tedious for me.
Re: Excellent software for mapmakers
RanDom v2
Province Editor
God Editor
Map Forge
Threaded Mode