Вот так и лишаются люди анонимности, даже КУС не нужен.
Даже если не брать что и в Москве и в других городах такие же биткоматы от той же компании и с тем же телефоном и пусть это будет Уфа, то вот интересно как потом искать человека без каких-либо данных о нем в городе-миллионике?

KYC это совсем другое и о другом, при KYC чаще спрашивают даже не адрес прописки а адрес фактического проживания через предоставление платежек за последние месяцы, и это действительно опасно если эти данные попадут в плохие руки.
Ну искать то его будут опираясь на криптоматы, ссылку на которые дал Ратимов, на территории России, а не по всему миру. Это как минимум сократит поиски в 2 раза, как максимум искать надо только в городах с криптоматом. И это будет лишь один из кусочков пазла. Копнут глубже, и список городов поиска сократится до 2-5. А там со временем сам пользователь, того не ведая, выдаст еще какую-нибудь подсказку.
Да могут найти легко, достаточно только лицо на камеру завсветить. Вспомните эти истории когда на митингах в омон стаканчик кинул и нашли. У них же есть уже средства, для таких поисков. Вспомнить тот же findface который закрылся для юзеров и прешел на гос работу.
Сейчас очень большой процент раскрываемости преступлений уличных, благодаря камерам, могут отследить передвижение по всему городу при удачном стечении остаятельсв, когда приехал и на чем, откуда вышел, куда пошел и т. д.
Вопрос в желании и возможностях того кто будет искать

Согласен. В плане определения личности современные технологии очень сильно продвинулись по всему миру. Особенно в Китае и США. Там за секунды камеры сканируют человека и тут же выдают всю информацию о нем.