There's actually a very controversial new EU doctrine that mandates telcos of all member countries to store "connection data" (I only know it by the German word "Verbindungsdaten", which encompasses when you called whom, which websites you visit, who you send email to etc, but not the actual data contained in those transactions) for at least 6 months.

While some countries (like, surprisingly, my native Austria) where actively against the new law for along time, in the end they caved to pressure from the EU (very unsurprisingly). Interestingly, the telcos themselves were against it, since they have to bear most of the costs themselves.

So yes, they do record everything you do, all the time, for everyone in Europe.

Edit: reading up on it again just now (I stopped keeping up on this stuff since it's just so damn infuriating/depressing), the EU doctrine is still much more contested than I thought, lots of countries still refusing to abide by the law. Though I fear they'll all cave eventually...

I imagine it would make sense to keep records for a few billing cycles. It wouldn't be unreasonable to have to deal with a customer dispute 3-6 months in the future. But I imagine it's also just plain easier to truncate the logs every six months or every year.