Столкнулся с таким на 1Gb, было это в 2010 году - проверенные имена оказывались зарезервированными. Принял для себя уйти от этого хостера, потому что они начинали брать деньги за любой чих плюс еще эти уводы имен...
Делал потом так: проверял имя на whois-service.ru , далее покупал на sweb.ru
Сейчас проще: ушел и оттуда, покупаю через GoDaddy, хостинг ЦифровойОкеан.
Кстати, о GoDaddy, интересный случай: покупал домен через сайт на мобильном. Ошибся в названии двух доменов (да, торопился, взял в двух зонах). Звоню в техподдержку, начинаю общаться с девушкой (на русском - несмотря, что компания иностранная, девушка с Болгарии), объясняю ситуацию. И вы знаете что? Она исправляет мне доменные имена на нужные. Представляете такой сервис в России? Я - нет :)
Потом мы еще общались с девушкой, но это другая история :) Но все в рамках профессиональных вопросов, не подумаете чего плохого :)
Ну а рег и прочее... я давно поставил на них крест. Бизнес в России в классическом понимании, мне кажется, невозможен.