А менять ли гражданство?
Я сначала по советам dimafogo именно так и делал.
У меня были случаи, когда при выезде из Украины, пограничники листая украинский паспорт просили показать визу (какое их дело?) Приходилось показывать немецкий паспорт. Не знаю что они при этом отметили в своей базе.
Был случай, когда меня патруль милиции остановил сразу после регистрации на рейс (по немецкому паспорту), я его еще даже не успел положить в карман, и прямо там у меня этот паспорт попросили показать. Стали зачем то искать там печать о въезде. Не нашли. Пришлось показывать им украинский паспорт. Это было в Одессе в 2014. Патруль с автоматами. Пережил несколько не очень приятных минут.
С тех пор въезжаю по немецкому и не имею проблем. Наоборот мне кажется что все пограничники/таможенники
общаются на порядок вежливее.