GPDR explicitly lets organizations keep data if they need to. Do you think it just turned into a magical get-out-of-your-past switch that means "my employer will have to delete records of firing me!"?
Your example "my employer will have to delete records of firing me!" is exactly how the GDPR works.
There are exceptions -e .g. if the firing is now leading to a court case, but they are less than you think.
In an ironic twist, after deleting the data subject's personal information, you must be left with nothing that identifies them, so you don't even know that they have requested this in the past - only that someone exercised their right to erasure (not who).
The right to erasure does not apply if processing is necessary for one of the following reasons:
to exercise the right of freedom of expression and information;
to comply with a legal obligation;
for the performance of a task carried out in the public interest or in the exercise of official authority;
for archiving purposes in the public interest, scientific research historical research or statistical purposes where erasure is likely to render impossible or seriously impair the achievement of that processing;
or for the establishment, exercise or defence of legal claims.
Article 17.1 The data subject shall have the right to obtain from the controller the erasure of personal data concerning him or her without undue delay and the controller shall have the obligation to erase personal data without undue delay where one of the following grounds applies: a) the personal data are no longer necessary in relation to the purposes for which they were collected or otherwise processed; https://gdpr-info.eu/art-17-gdpr/
If you read further down the page, you come to the section you are quoting, 17.3, which says that the above right from 17.1 does not apply even if one of the conditions in 17.1 is met. However the scenario we are talking about is one where none of those conditions were met in the first place, so we never had to look at 17.3.
You can argue that 17.1.b/c would require an employer to remove any demographic/political data it had stored on you, but absolutely not that it requires the employer to remove the record of your existence at the company.
17.1.b appears to be the trump card held by the data subject. They can withdraw consent at any time and request erasure.
Once they do, the data controller can then use any of the exceptions in 17.3 to deny them. However none of these is "because I want to keep records of all firings".
My further understanding is that you certainly could keep a record that someone was fired, just not a record that included any personal information that could identify who that was.
i.e. pseudonymization..
(edit - and I think you could keep the information about their race/etc if it was properly pseudonymized, but I haven't tried working that out so I'm not sure).
In other words, GDPR has no teeth outside of Europe.