Моя success story:
Сам с небольшого южного города, расположенного на берегу Черного моря. Уже обладая достаточным опытом работы в позиции мидла (C#), столкнувшись с проблемами автора вопроса, выложил резюме на hh.ru, получил кучу звонков от эйчаров. Прошел серию собеседований по скайпу, остановился на одной компании, получил от нее оффер. Удаленно с помощью cian.ru нашел квартиру (благо было кому посмотреть и передать агенту деньги). Правда своих сбережений на переезд не хватило, пришлось взять кредит, но довольно быстро его погасил. Пожив в столице больше года и прокачавшись до сениора понял , что такой климат и ряд условий проживания меня не устраивают и вот подумываю о возвращении назад.
Success story знакомого (тоже .Net-чик, тоже с города на берегу Черного моря):
Приехал в Москву, в течение 2 недель прошелся по собеседованиям, делая упор на поиск удаленной работы, нашел такую с сеньерской позицией, прошел испытательный срок 3 месяца в столице и вернулся назад, к морю и теплу.
Кстати по статистике odesk, в Краснодарском крае прям сосредоточение удаленных работников этой биржи.