При посольстве нотариусы есть украинские, вам консул не нужен, а нотариусам абсолютно все равно какой паспорт и с какой пропиской. Кстати вписать можно загран там только код подразделения выдавшего, прописки не видно. Через крымско-украинскую границу я не ездила, не знаю, но я еще когда была гр.Украины в Калужской области и в Москве спокойно оформляла у местным русских нотариусов согласие, ни у кого вопросов на границе не возникало.