Имеем два компа, находящиеся в разных подсетях.
На исходном компе Visual Studio 2012, Win7x64
На целевом компе (проверялось на Win7x64 и на WinServer2012x64) папка, скопированная с первого компа из:

Сначала пробуем просто подключиться отладчиком к целевому компу, ожидаемо получаем ошибку подключения.
Далее на целевом компе запускаем msvsmon.exe
Пробуем в двух вариантах:

1) Оставляем msvsmon.exe в режиме Windows Authentication , на исходном компе в Attach to process оставляем transport: default , пытаемся подключиться по IP (или IP:Port), на исходном компе появляется окошко авторизации. Вводим домен\логин и пароль целевого компа, имеющего права на удаленную отладку (логин есть в списке, который открывается в Permission в msvsmon.exe), получаем ошибку.

2) Переключаем msvsmon.exe в режим No Authentication - Allow any user to debug , на исходном компе в Attach to process ставим transport: remote (no authentication) , пытаемся подключиться сразу получаем ошибку.

В обоих случаях ошибка одинакова:
Unable to connect to the Microsoft Visual Studio Remote Debugging Monitor named '*************'. The Microsoft Visual Studio Remote Debugging Monitor (MSVSMON.EXE) does not appear to be running on the remote computer. This may be because a firewall is preventing communication to the remote computer. Please see Help for assistance on configuring remote debugging.

В других комбинациях:
- transport: remote (no authentication) + msvsmon.exe Windows Authentication - ожидаемая ошибка Ensure that the remote debugger is running in 'No Authentication' mode.
- transport: default + msvsmon.exe No Authentication - Allow any user to debug - ожидаемая ошибка Ensure that the remote debugger is running in 'Windows Authentication' mode.


Из вышеизложенного очевидно, что исходный компьютер видит целевой комп, в частности реагирует на изменения режима аутентификации.
Компы находятся в разных подсетях. Внутри одной подсети отладчик подсоединяется к другой машине без проблем в любом режиме.

Что может мешать? Если даже где-то в сети режется трафик, то что именно может резаться? Ведь вроде как обмен идет только по TCP по конкретному порту (порт, кстати, тоже пробовал менять - картина не меняется), телнет тоже коннектится к целевому компу. Нагуглить по данной ошибке тоже ничего не смог - везде стандартные советы, проверьте, что запущен msvsmon.exe и т.п.

Попробовал с VS2015 - все работает.
Но нужна 2012...

Вот эту статью почитал
https://msdn.microsoft.com/ru-ru/library/9y5b4b4f(v=vs.100).aspx

Попробовал запускать под одинаковыми локальными админами. При этом он даже не спрашивает пароль при windows-аутентификации, но дальше опять та же ошибка.