Что делать, если недобросовестный хостер заблокировал VDS?
Съезжайте оттуда.
Правомерно ли - читайте их TOS. Скорей всего там это обговорено, так что да, правомерно.
Нормально ли - нет.
Как посветовали выше - читайте TOS. Просите бэкап. Судя по всему у вас OpenVZ контейнер, можно возможно от них получится сторговать vzdump архив. 
Однако, странно. Какую именно они нагрузку имеет в виду: на сеть, на диск, на процессор?
Конечно. если у вас там постоянно работал dd или вы майнили биткойн я еще могу понять хостера, но я бы на их месте предоставил хоть каких-либо данных.