У меня знакомец когда-то такое сделал - переезжал между районами в пределах Киева. Сказал, что крайне гиморно, проще было закрыться по старому месту жительства и заново открыться на новом месте. Но дело было давно, могло уже измениться. Думаю, что имеет смысл начинать с визита к госрегистратору - они расскажут дальнейший порядок.
У меня жена проходила эту процедуру, но не сама, а девочка, которая проф. занмается регистрацией/перегистрацией бегала и все делала. Заняло по времени 2-3 месяца с учетом всех фондов и налоговой и по деньгам около 2,5 тыс. грн. (были некоторые нюансы с пенсионным).
В 2007 сам все делал,из Киева в область.Вроде сначала к регистратору,потом в свою налоговую с заявой,налоговая даст временную 4опп уже на новое место жительства,потом в ПФ заяву.Дальше уже в новую налоговую и ПФ.Ничего лишнего по деньгам и никаких проверок.