if your explorer is aboard a ship, it works, as he's contiguous from a (sea in this example) area
believe me, it works, did it with Prussia for Solomon, Bismarck Archipelago (Rabaul) and New Guinea (Lae, then others area) - safer, and quicket to embark/reembark than move from land in little developed areas (historical and accurate)
like Africa, I never explore risking my precious irreplacable explorer, he acts from adjacent area - sea or from land protected by colonial army - slow but methodical, else you could never explore easily and safely (in "real terms", he cautiously secure routes , establish maps, make small raids, and don't go adventuring in wilderness without a (safe) way back
or you can send him in unexplored area, I believe it's possible but risky
only 2 problems :
a) you need to keep your ship here a few succesive turns (in addition of failed attempts) as decision takes a few (6 I believe) ones to implement - and your ship can take many hits in the process (if he's lost, your unit aboard is too) as well as cohesion (just try to go home with a cohesion zero ship from a far from base sea area and you'll understand quickly what I mean )
b) exploration is very costly, and comes in direct concurrence for economic development - useful for late game, or being the first in strategic areas, or to get exotic assets to increase your population contentment (exotic fruits, coffee, diamons, gold, you'll rarely fiond in Europe and are sond in world market in few quantities)
else you have this :
http://www.ageod.net/agewiki/SetKnownRegions