Вроде УФНС делает Конкурсы на это.
C ИФНС надо было договариваться вручную. Некоторые УФНС нормально относятся к любому претенденту, у которого есть все документы. А иногда приходит контора со всеми лицензиями, а ей отказывают - у нас уже есть договор с другим, а у другого ни лицензий, ни специалистов.
Тут сильно зависит от ситуации с количеством налогоплательщиков, сдающих отчетность в эл. виде в конкретном регионе. Если их много, то УФНС будет новых СОСов посылать, если мало - УФНС будет только радо новой крови.
Про получение лиценций на телематику - на этом форуме полно сведений.