About the scouting issue, I think we may be able to poach an idea from EU. Ships at sea suffer from attrition based on how long they are at sea, and if they are gone too long, the whole fleet will be gone. Maybe we could do a similar idea here. Units outside of your cultural borders get, say, 10 turns of free movement, after which they take a steady 20% damage/turn until they die (these values should be adjusted, obviously). Walking through territory for which you have OB can either cause no attrition (they are letting you in, they will probably share with you), or, what I would prefer, the attrition is lowered. Maybe set a certain condition for which you can send units free of attrition (like having a defensive pact). Maybe scouts/explorers can have more free movements and/or less attrition. Something like 20 free + 1/2 attrition for scouts and 25 free and 1/3 attrition for explorers. The attrition could also be set based on tech level, so a low tech civ will lose units quickly while civs with, say, electricity or refrigeration, will be able to move far into unknown territory/enemy territory without seeing their units wither to nothingness.
This can be used to simulate attrition from wars, too. Maybe Russia's UP can be much higher attrition % values now, or we can come up with another UP altogether.
Lastly, this simulates one of the motivations for settling patterns seen in real life. South Africa and several Pacific islands were colonized to serve as refueling bases for ships. Not having to stop every few turns to "refuel" is something I've always thought funny about Civ, you can have a floating city of doom that never needs to see land.