How does settlement for EU nationals in third countries within EU work?

Directive 2004/38/EC was already mentioned but it's worth quoting it because it's highly relevant:

The fundamental and personal right of residence in another Member State is conferred directly on Union citizens by the Treaty and is not dependent upon their having fulfilled administrative procedures.

Persons exercising their right of residence should not, however, become an unreasonable burden on the social assistance system of the host Member State during an initial period of residence. Therefore, the right of residence for Union citizens and their family members for periods in excess of three months should be subject to conditions.

For periods of residence of longer than three months, Member States should have the possibility to require Union citizens to register with the competent authorities in the place of residence, attested by a registration certificate issued to that effect.

For example Austria executes this practically word-by-word: allows EEA/Swiss citizens to reside up to three months without conditions and after three months there are conditions, read the link. What is relevant to the question is

EEA citizens and Swiss people who have a right of residence for a period of more than three months according to Union law and are staying in Austria longer than three months must report their taking up of residence to the residence authorities. A registration certificate [Anmeldebescheinigung] as documentation of their right of residence will then be issued upon application. Such an application must be made within a four-month period starting from the applicant's arrival in Austria.

Formally, EU citizens never need a permit to secure the right to stay in another EU country. They just need to fulfill the conditions defined in the treaties and the secondary law implementing them (directive 2004/38/EC, CJEU case law, national laws and regulations). If you do fulfill these conditions, the country has no discretion and can only ask you to leave for very specific reasons (“public policy, public security, or public health”).

To the extent that some formalities or documents were (or still are) required, they are supposed to verify that you do indeed hold a (pre-existing) right to reside and not constitute a permission. Concretely, this means that failing to request such a document in time can, at most, result in a fine (and a bit of confusion when interacting with the authorities) but you would not be accruing illegal stay or risk losing your residence rights. That's also why they are often called a “card“ rather than a “permit“, like the residence card for third-country members of the family of an EU citizen (which is, however, required).

Twenty or so years ago, freedom of movement already existed but directive 2004/38 wasn't implemented and case law was less extensive and it was still common to routinely issue or even require some sort of residence document. I held several of these from various countries. Nowadays, most countries dropped this requirement and do not routinely expect you to get one but some still offer it.

For example, you mentioned France and you are right that it doesn't require any formalities from EU citizens. Since there is no national registration system, you don't even need to report your address anywhere and can simply take up residence in the country. However, you can still get a residence card, free of charge, if you wish to document your status. Such a card looks like a residence permit (blue/pink plastic card) and can be used in lieu of a passport or ID card for just about any purpose in France.

In Belgium however, you are supposed to report your address to the authorities within 10 days and to submit some evidence that you do qualify for freedom of movement rights. You then get a “proof of registration”. That's the 3-month document you heard about. During these three months, the municipality is supposed to check that you do live at the reported address and possibly refer your file to the federal authorities if additional verfication is necessary. It would then issue a “certificate”. That's the 5-year document you heard about. While it is actually a small plastic card with a chip that looks and feels like a residence permit, it is emphatically not called a “permit”.

As long as the formalities are similar to registration requirements applying to their own citizens, other EU countries are free to impose requirements like those that apply in Belgium (which seems to be more fastidious than most however).

After five years as a resident in another EU country, you should also be considered a “permanent resident”, which comes with additional rights and protections. That's one reason why the original certificate is valid for 5 years. Because establishing you're a resident and ultimately securing permanent resident status are advantageous for you, it makes sense to apply for the relevant documentation even when that's not required.

Legally, you do not need any permission to become a (permanent) resident and your status doesn't depend on it but documenting it will make things much easier if you want to depend on it down the line (e.g. if you become unable to work and need some sort of welfare support).

It might depend on a country-by-country basis. But at the same time that difference is not in applying for residency (as EU citizens have the right to reside in another EU country by law, therefore they don't need to apply for this right per se) but rather following local laws to correctly execute their rights to live in that new country.

Estonia

For example, this is what is required in the case of Estonia:

You must register on the Estonian Population Register if you’ll be in Estonia for more than 3 months and apply for an ID card. All Estonian citizens and residents over 15 must have an ID card.

Source: https://www.gov.uk/guidance/living-in-estonia#visa-and-residency

Please excuse me for using a non-official source (provided by the UK government, as I couldn't quickly find an Estonian page that explained it the same way) but it is true that every adult resident has to have an Estonian ID card by the Estonian law, therefore a EU citizen will need to register with the authorities and be provided with an Estonian ID card. All the data is centralised (kept in the population register), therefore, for example, if you decide to see a dentist, as soon as you give them your ID card they will see your relevant information (for example your current address where you live).

UK

However, in the case of the UK (before Brexit aka whilst it was a EU country!): You do not need to register with the authorities. You can live forever in the country without having to register or make any such application.

Normally, you would acquire permanent residency automatically after 5 qualifying years of living in the UK, and then can optionally apply for a "document certifying permanent residence" to prove this status. People before Brexit have lived for 20+ years without applying for this document, as it wasn't necessary. It would normally be mainly useful for an application to naturalise as a British citizen, and even then, in the past it was allowed to naturalise without applying for the permanent residence document. So you could technically arrive to the UK and then apply for naturalisation 6 years later, without anything in between.

A EU-Citizen cannot apply for or receive a residence permit in another EU-Country.

They are, however, required to conform to the local residence laws - which can differ from country to country and also apply to citizens of that country.

One difference is that after 5 year of residency, a permanent residence document can be applied for (but is not mandatory).

See link below for more details, where this may be beneficial.

---

Sources:

• Permanent residence (after 5 years) for EU nationals - Your Europe