Partially-illustrated-style Fantasy Campaign Setting World Map

Subject
The idea is that this is a world map for a Dungeons & Dragons-style fantasy campaign setting, but only depicts one partial continent (probably roughly the size of the UK, maybe a little bigger). The "twist" is that this map should incorporate some stylized artwork of various sites and features depicted on the map, rather than being strictly a map of geographical terrain and a black square with a city name next to it. (Examples of the style below.)

The particulars are that there will be seven "regions" of the map, one of which is a city (mostly in ruins, and immensely huge, about the size of Rhode Island). The non-city regions are mostly made up of a single dominant terrain type -- i.e. Mist Shorn is mostly swamp with some trees, Ashen Sands is all desert -- but all of these regions have impossibly fantastic sites or features within them. Things like flying islands, pillar-like mountains, valleys with miles-long dams, a tree that could fit several cities, Grand Canyon-like rents in the earth that are as deep as the Mariana Trench; that sort of thing. Those specific sites and features are what will be featured on the map in a somewhat stylized manner.

Additionally, one of those seven regions exists literally at the edge of the planet: a peninsula and the ocean around it are torn apart, leaving floating bits of ocean and islands floating in space. Yeah, it's a little weird.

Style
I am looking for a map in the following style:
http://www.fwallpaper.net/wallpapers...1_1280x800.jpg
http://vignette2.wikia.nocookie.net/...path-prefix=ru

Mainly that first link. Some maps of Terry Pratchett's Discworld might also illustrate a similar style.

Scale is not important at this stage, but it won't hurt to think in terms of scale in case this project turns into something ongoing down the line. In other words, you don't have to stick to some strict scale and put such a scale on the map, so long as the map fits all the areas described and looks awesome.

Quality & Size
Professional, required for print (8.5 x 11) & web.

I'm not fully clear on technical details for artwork beyond that. Feel free to ask and advise in your response.

Time Constraints
There is no strict deadline for this request; please provide reasonable estimates in your response. If you work with multiple draft/phases, feel free to give estimates at each phase of the project.

Copyright
I will have the right to use the image for commercial purposes, the artist will have the right to exhibit the image as part of his portfolio but not to exploit it for commercial gain. The long-term idea is that this will end up in a product on DriveThruRPG, though for now, it will remain private (or, at most, shared on neuronphaser.com) until such time as I finish writing the campaign setting ;-) By taking on this project, you will allow me to use the map for these stated purposes.

Payment
I'm looking for estimates on both pay and time, and I'd prefer to pay via PayPal, once the commission is complete. I have worked with artists before -- Elena Naylor is one -- but never on maps, only illustrations and digital illustrations, so this is a little new to me.

Contact Details
tjbannock--at--gmail--dot--com
(remove the -- and convert "at" to @ and the "dot" to .)