> Germany has one of the shorter retention periods at 10 weeks, but they still have to keep those records.
No they don't, because it's "suspended" by the federal network agency until courts are through with it. In fact they suspended it three days before the law would've come into force and thus it never was. The current state of affairs is this: the retention was ruled incompatible with German and European law in an injunction and it does not look like that is about to change.
There's a similar picture in many EU countries: There's a law on the books, but it can't be enforced/is being challenged/was already invalidated/is being rewritten/repeat.
Also note that to courts location data/phone records is a different issue than retaining information that merely associates an IP address with the subscriber that used it at some time (knowing which subscriber has what phone number is not an issue either, after all). The latter was ruled to be unproblematic by the ECJ just this year, while for the former the latest ruling is what I outlined earlier.
Besides Germany, some other countries that had data retention laws that were ruled unconstitutional are: Belgium, Bulgaria, Czech Republic, Cyprus, Romania, Slovenia, Slovakia.
In many other places that currently do have mandatory retention in force, it is being challenged.
> Saying that it would be illegal to collect these records in Europe is patently false
It is illegal to mandate in such a manner. There's a difference.
> Billing. You need phone records for billing purposes. You need to keep them for a while longer because people will dispute their bills all the time.
You must've not read the part where I said "beyond what is necessary to operate". Telekom for instance is doing just fine deleting phone records after 80 days - or within 7 days if you use a flat-rate and they're not relevant to billing.