Хотя ни один законодательный акт (ТК, 115-ФЗ, и тд) не требуют - сотрудники УВМ настаивают именно на увольнении и последующем приеме. Если есть время - проконсультируйтесь лично (и желательно письменный ответ получить... который мне, например, получить не удалось ни разу), но в Москве в большинстве отделов только так..
Если учесть, что в СПб вообще уведомления о приеме/увольнения только через почту, то разницы особой нет...? Главное, чтобы успел получить РВП до окончания срока патента + регистрацию (!!!)