Speaking as one who’s studied Russian for 15 years now, J. Harvard, I can say for certainty that no Russian, be s/he from Moscow, Leningrad, Omsk, Tomsk, Volgograd, or Magadan, calls it “THE Ukraine”.
Whyzat? 'Cos Russian doesn’t have a definite article!
Having said that, you’re more on the mark with the origins of the word ‘Ukraine’, since ‘at the border’ in Russian is ‘u kraia’, so ‘Ukraina’ is probably some sort of collective noun meaning ‘borderlands’.
The Nether Lands were probably given a ‘the’ by Britain 'cos I’ve never seen the Dutch use it themselves. At least on any of their soccer gear (they, or at least some of their fans, were here in DC for the 94 World’s Cup). I always thought it was neat that the three languages of the countries that border the Netherlands have the same name for 'em in their own tongue: The Netherlands, Les Pays-Bas, and Die Niederlanden (all ‘The Lowlands’).
Cave Diem! Carpe Canem!