Брал год назад наносим в главном офисе NCELL в Krishna-Tower. Сейчас не знаю, может и полегче с ними и в других офисах. Лучше обращаться в большие и официальные, например на Дарбар-марг.
Если в горы, то одназначно лучше NTC (NepalTeleCom). Самый широкий охват. Но про мобильный инет у них не в курсе.