Looks very good as is but I think adding the clues would fun. If you add them to the border, as you suggest, just make sure you don't get to heavy and dark with the line work. Right now your border is fairly light and adding sone details may just help make it look more unified with the map. The border is a frame sure but it's also part of the overall composition. You just don't want it to over power the map. Don't know if that's helpful, but good luck.