Я просто помню, что Украина и Куба были исключениями из правила. Во все остальные страны едут "в", типа, в Германию, Англию, Америку и пр. а вот с этими двумя странами "на" - на Кубу и на Украину. Соответственно и обратно - возвращаются/приезжают из Германии, из Англии и из Америки, но с Кубы и с Украины. Мы же не говорим "вернулся ИЗ Кубы" - оно просто режет слух. Вот и с Украиной должно быть, что с Украины, потому что это исключение из правила.
Даже просто на слух к "в"(нутрь) больше подходит "из"(нутри), а к "на" больше подходит "с".
В общем, моя имха - когда говоришь "в" - то обратно логично, что "из". А если уж сказал, что "на" - то обратно только "с".
Я думаю, что путаница возникла именно по причине украинского изменения в 1993 году. Сначала было продавлено это "в", а за ним потянулось разумеется и "из". Потом русскоязычные вспомнили что по правилам русского языка оно всё равно "на" и от указа президента (или кого там?) новой назалежной русский язык-то не изменился и стали говорить "на", а вот это "из" оно как-то зацепилось и осталось. Имхо, конечно.