В октябре и ноябре 2008 г. нам были выставлены счета-фактуры за услуги связи. В феврале 2009 г. были выставлены счета-фа

Недопустимо внесение исправлений в счет-фактуру путем повторного выставления продавцом счета-фактуры по товарам (работам, услугам) , в отношении которых ранее был выставлен счет-фактура.
Письмо Минфина России от 01.04.2009 № 03-07-09/17).
В случае обнаружения нарушений в составлении продавцом счета-фактуры исправления вносятся в данный счет-фактуру (п. 29 Правил ведения журналов учета полученных и выставленных счетов-фактур, книг покупок и книг продаж… , утв. Постановлением Правительства РФ от 02.12.2000 № 914).

Вам нужно в том налоговом периоде внести изменения в книгу покупок:
- на дополнительных листах сделать запись об аннулировании неверных счетов-фактур и записать верные
-сдать уточненные декларации по НДС.

Ваш поставщик не прав. Нормальный порядок в таких случаях - не изменение ранее созданных документов, а создание новых по факту пересмотра стоимости услуг за прошлые периоды. Вы уже отразили в книге покупок счет-фактуру, приняли к зачету НДС, и факт пересмотра задолженности не должен повлечь для вас корректировки предыдущих периодов.

Экономическое содержание данной операции - соглашение между сторонами или решение о пересмотре стоимости ранее оказанных услуг. Соответственно, на дату такого соглашения и должны быть подготовлены первичные документы и выполнены проводки. На мой взгляд, лучше всего было бы на основании данного соглашения восстановить НДС в текущем периоде на основании полученной корректирующей счет-фактуры, и отразить бух. справкой дополнительный доход как прочие внереализационные доходы, чтобы учесть в целях налогообложения прибыли. Таким образом, оправдываться перед ИФНС по НДС будет поставщик, так как он допустил нарушение и обязательно получит за это налоговые санкции, а у Вас всё будет в соответствии с законом.

С другой стороны, если сумма снижения стоимости услуг позволяет уплатить пени и неоплаченную в бюджет часть НДС и налога на прибыль, то можно скорректировать и исходную счет-фактуру, исходные акты, и подать корректирующие декларации по НДС и налогу на прибыль. Но я не стал бы этого делать, чтобы не создавать себе лишних проблем :)

В периоде октября и ноябя делаете Доп лист в книгу покупок и сдаете уточненную декларацию по НС.
Соответствено - уточненную декларацию по Прибыли за 2008 год.
А проводки в бухучете делаете текущей датой.