I can comment from the point of view as a purchaser like your self.
1 - I figure out what my budget actually is. Can I afford to spend $25 for this piece of art? Can I afford $500?
2 - Is the piece for your own use in your own game like mine are, or do you want to use them for a commercial purpose? Letting the artist keep the copyright and you only retaining the right to personal non-commercial use will help the potential artists decide if they want to tackle the project and also how much to charge for it.
3 - How fast do you want this? Remember the basic rule of design: you can have it quick, cheap or correct - pick any two.
4 - Be flexible in choosing what you want. Want a full blown continent map with detailed area maps? Or is it more important to have that one detailed area map first then hire again for future maps of adjoining areas? Based on budget it might be worthwhile to commission them all at once from the same artist or do them consecutively over time.
5 - Be clear on what you want based on the above criteria. Give examples if you have them, because that will determine how long it takes someone to produce a particular style.
I have had very good results from my hires here on the Guild and also on eLance. Two examples for you.
Final Result: http://www.dragonslayers-society.org...=Main.Outreach
Final Result: http://www.dragonslayers-society.org...end-CityProper
I have used many other maps I have purchased from the very talented artists here in the Guild but I hope these examples help you formulate your own request strategies.