нотариус отказывается оформлять доверенность на продажу недвижимости ввиду отсутствия прописки в паспорте - правомерно?

Нет.
Место жительство - только при наличии.
===================
6.2. Доверенность должна содержать:

- наименование документа;

- указание на место ее совершения (город (село, поселок, район), край, область, республика, автономная область, автономный округ полностью), а в случае удостоверения доверенности вне помещения нотариальной конторы - также адрес удостоверения;

- дату ее совершения (число, месяц и год совершения доверенности указываются прописью) (п. 1 ст. 186 ГК РФ, ст. 45.1 Основ);

- сведения о представляемом и представителе: в отношении физического лица должны быть указаны фамилия, имя и (при наличии) отчество полностью, место жительства (при наличии); в отношении юридического лица - полное наименование, адрес, место нахождения и (при наличии) регистрационный номер (ст. 45.1 Основ);

- полномочия представителя (ст. ст. 182, 185 ГК РФ);

- подпись представляемого или представителя юридического лица (ст. 44 Основ, п. 4 ст. 185.1 ГК РФ);

а также может содержать:

- срок, на который она выдана (ст. 186 ГК РФ);

- указание на право или запрет передоверия, возможность или запрет последующего передоверия (п. 1 ст. 187 ГК РФ).

Просите письменный отказ, а там видно будет...

Отсутствие регистрации никоим образом не умаляет права собственника на распоряжение собственностью.
Конечно, незаконно.
Письменный отказ не получите однозначно, так что обращайтесь к другому, более грамотному нотариусу

ну вообще это один из способов идентификации лица

Нет не правомерно. Просто обратитесь к другому нотариусу.

да

вообще прописка лет 25 уже не правомерна (в разрез с конституцией она), сходите к юристу, чтоб не метаться, всё быстрее чем её делать и спокойствие будет