Bitcoin и аналогичные криптовалюты

Да, неплохой вариант. Но есть определенные минусы, которые не позволяют всерьез опираться на Биткойн. Например, курс по отношению к основным валютам. Вообще, события на Кипре напоминают, сколь все зыбко в финансовом мире. Имейте это ввиду.

ААХ стОящий он и стОит соответственно. В таком случае проще и целесообразнее (в финансовом отношении) создать скрытый сервис в Tor (вангую траблы с посещаемостью) на ваших серверах и там поднять портал по борьбе с произволом чиновников от ЖКХ!
Опасное это дело. Некоторые мэры, Царствие им Небесное, знают знали это.

А что потребуется от меня, в смысле, какие данные я должен открыть, чтобы открыть счет в Либерти или Перфект?

В данном случае, как принято говорить, левые данные. Более-менее правдоподобно выглядящие.
Полистайте на досуге русскоязычный мануал по ЛР. В частности 1, 2, 3.
Многое там уже устарело, но информация общего характера актуальна и дает представление о ЛР.

какие наиболее распространенные электронные платежи принимают зарубежные хостеры, при которых не утрачивается анонимность плательщика

Карты VISA/MasterCard, ЛР, ПМ, PayPal.
Если хотите анонимно оплачивать, в данном случае надо иметь на руках платежный инструмент, зарегистрированный не на себя. В каких-то случаях на реальное лицо, т. н. дропа, в каких-то на виртуальное. Соответственно, в определенных случаях есть риск блокировки счета или требования подтвердить свою личность. В т. ч. и сканами и т. д. Но это скорее форс-мажорная ситуация. ЛР одно время прославились массовой блокировкой счетов. Но это специфическая система, она и создавалась для всяких таких безотзывных транзакций:) Можно сказать, что все эти платежки для оперативных платежей на мелкие и максимум средние суммы. Хотя у многих на счетах в них сотни тысяч зеленых. Опять же, потом они оперативно выводятся, переводятся, обналичиваются.
А анонимность по определению, по умолчанию – это только биткойноподобные валюты. Все остальное не анонимно, но может быть использовано псевдонимно.

Ведь нужно выбрать какой-то конкретный, наиболее оптимальный для ААХ вид платежей, и остается вопрос – какой именно?

Тот, который принимает ААХ, который вам подошел, на котором вы остановили свой выбор.

на самом самом последнем шаге с вас потребуют номер сотового для контрольного звонка :((

Вы не Вконтакте регистрируетесь. Да и там вроде сразу предлагают ввести номер мобильного. Левый мобильный с левой же симкой – около 800-1000 рублей.

Все бы ничего, если бы право и закон соответствовал знаменитому dura lex, sed lex. Я наблюдаю иную картину не только в России, но и в других странах. Кто пишет закон и для кого, кто контролирует его исполнение?) ЕС, США, демократия. Ага. Счаззз. Как высказался один деятель государственного масштаба, демократия бывает только управляемой. Там где можно решить вопрос демократическим путем, там он так и решается. В остальных случаях идет отступление от основополагающих принципов демократии, что мы и наблюдаем сейчас на Кипре. Я надеюсь, все держат в уме долги США?))

Поэтому иногда имеет смысл в здравом уме и трезвой памяти регистрировать счета не на себя (на виртуальное лицо, на дропа, на доверенное лицо). Вовсе не обязательно при этом использовать их в серых или черных схемах.

P.S. Полистайте в свободное время – http://hosting101.ru/
ААХ подскажет Гугл или Яндекс, чтобы не рекламировать их здесь. Особой уверенности в них нет, т. к. в паблике годноты немного. Листайте всякие форумы типа античата, к примеру. Там можете зацепиться за нормальное предложение нормальной услуги. От кидал также не застрахован никто. И все, абсолютно все телодвижения минимум через Tor, дабы сохранить инкогнито.