The territory names are very small, no results with 'WhatTheFont!'.
Slightly larger original image: http://i.stack.imgur.com/RS9LU.jpg
This is killing me, I know that font. The only name that is coming to mind is Frutiger's Ondine. Not quite it but it has a lot of the qualities you're going for.
If the match comes to me, I'll update here. It's going to keep me awake tonight!
Pompeijana comes closer in some respects. Maybe this is what I had in mind, but the
UPDATE TO THE UPDATE
I just had to go look one more time, following the Pompeijana thread. I know this also is not a perfect match but it is closer in some respects: Pompeii Caps. It's not as well drawn as Pompeijana but it is free!
The oceans are easy: that's Lucida Blackletter (stretched). The country names look very similar to "FinalRoman Medium", but that doesn't have a capital P like yours. However it would be a decent match if the right font can't be identified.