Isn't exploration doing/going in 'chunks' of sea/land? And as such - when you have colonial range to 'explore' at least part of it - it then allows you to explore 'entire chunk'? And the colonial range of coast may actually be counting the range to the nearest sea tile near that land chunk?
Having range to "part of" the region doesn't let you explore all of it, only the part you have exploration range to. This is easily confirmed as you'll see the same region pop up in the exploration menu a couple of times as your range increases. If you explore it once, without enough range for all of it, it comes up again after your range increases.
Exploration range is definitely greater than colonial range and outside of supply range. I think you can still manually explore with fleets, you just run the risk of sinking due to attrition because it'll be outside of supply range. As for the coastal exploration missions, no idea if the range is different or not.
I bet a modder might know how the exploration range is calculated...