Но чуть позже, когда я подал документы на выписку, мне сказали, что у меня сть еще один какой то долг за 2004-ый год.

Михаил! По закону снятие с регистрационного учета никак не связывается с долгом по коммунальным платежам. Препятствование в снятии с учета по данному основанию - незаконно. Кроме того, долг за 2004 г. находится за пределами срока исковой давности.

ГК РФ

Статья 196. Общий срок исковой давности

Общий срок исковой давности устанавливается в три года.

Статья 200. Начало течения срока исковой давности

1. Течение срока исковой давности начинается со дня, когда лицо узнало или должно было узнать о нарушении своего права.

Статья 199. Применение исковой давности

1. Требование о защите нарушенного права принимается к рассмотрению судом независимо от истечения срока исковой давности.

2. Исковая давность применяется судом только по заявлению стороны в споре, сделанному до вынесения судом решения.

Истечение срока исковой давности, о применении которой заявлено стороной в споре, является основанием к вынесению судом решения об отказе в иске.

Постановление Правительства РФ от 17.07.1995 N 713

(ред. от 21.05.2012)

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

31. Снятие гражданина с регистрационного учета по месту жительства производится органами регистрационного учета в случае:

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

33. Органы регистрационного учета на основании полученных документов снимают граждан с регистрационного учета по месту жительства в 3-дневный срок.

Отметка в паспорте гражданина о снятии его с регистрационного учета по месту жительства производится в день поступления в орган регистрационного учета документов.