My linguistic intuition - going a bit ahead of the dictionary (as I think would be the case with many other contemporary Russian speakers) has chosen из Украины
It's not result of intuition, it's result of mass media intervention. Many politics and especially diplomats says "из Украины" and "в Украину". Even Lavrov does that! So we hear this variant often and many people really think that it's correct. No, it is not. When I studied at institute our teacher warned us if you take an exam, don't say "из Украины" and "в Украину" because it's a mistake.

my mind is split between tradition and the modern situation that Ukraine is an independent state
If we have to be guided by the political situation to select an prepositions, how we should say:
"Кому на Руси жить хорошо?" - traditional variant
or
"Кому в Руси жить хорошо?" - variant, wich bases on modern political situation.