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).