Keine Rechnung erhalten - Mahnung

Ich habe im Internet eine Dienstleistung in Anspruch genommen welche mich 9,95 Euro kostet.(Am 11.02.2004) Der Anbieter wies mich darauf hin das mir eine Rechnung zugestellt werden würde damit ich den Betrag begleichen kann. Monatelang war nichts zu hören bis ich dann 7 Monate später ein Mahnschreiben von einer Anwaltskanzlei bekam mit der Mitteilung das die Forderungen mir gegenüber jenem Dienstleister seit mehr als 30 Tagen offen stehen. Es werden Verzugszinsen sowie 39,00 Euro(!) Gebühren berechnet. (Anwaltskosten sowie Auslagen) Bei Nachfrage bei dem Internetdienstleister wurden mir laut deren System zwei Rechnungen geschickt welche ich jedoch nie erhalten habe. Ist die Forderung rechtens? Muß ich deren Anwalt bezahlen und in dieser Höhe? Was ist wenn die Rechnungen auf dem Postweg verloren gegangen sind?