Почему провайдеры не могут заблокировать VPN?
Почему не могут-то? Могут. Просто такой команды пока не было. Погуглите, как с этим в Китае, например (с работой VPN). Или Вы думаете, тот факт, что Shadowsocks - китайская разработка - случайность? :)
Ну и кроме того, не всякий VPN - это обход блокировок. В энтерпрайзе - это обычная технология обьединения филиалов с головным офисом и предоставления удаленного доступа сотрудникам.

Предложил изменение вопроса - убрал тег "Шифрование"
В чем тогда проблема для провайдера просто блокировать все зашифрованные запросы?
Это противоречит действующему законодательству. См. законы о предоставлении услуг связи и о предоставлении телематических услуг. 

Провайдер может блокировать трафик только в случае, когда он чётко знает, что данный трафик должен блокироваться. Блокировать всё подряд выглядящее подозрительным - путь, в конце которого можно найти лишение лицензии. А если и нет - то всё равно большую кучу проблем. Поэтому провайдер будет соблюдать именно букву, а не дух.