I too think the key looks great in the lower/middle area of the map. One thing you might do to improve the 'balance' of the whole thing is to move the scale bar directly beneath the key. You'd have to overlap that lower continent with it, thus covering up some details of that land mass, but it seems like the focus of the map is on the northern continent anyway. Maybe just 'generalize' the feel of the southern continent, with no mountains and less names, so the scale bar doesn't appear to cover up too much and/or look jarring with stuff poking out from underneath it.
All in all though, a very awesome map. Mountains look especially good, and varying the line width on the coastlines was a good call.