Do countries without exit immigration check (like US or any other one) know you have overstayed when you're leaving the country?
Sometimes, but not always. For example, if you leave the US by air, the airline will provide your passport information to the US government, but not everyone leaves the US by air. If you leave by land to Canada, the Canadian government will share information about people entering with the US. But, as of 2023, the Mexican government does not share information about people entering with the US. (See this Congressional Research Service report, page 11 (14th page of the PDF).) Therefore, if the US government does not have a record of someone leaving, it may not be able to distinguish between someone who is still in the US, and someone who has left by land to Mexico.
And if not, does that mean that this overstayed person can easily come back to the same country later on a new valid visa or passport without being detected by the enter immigration and let in with no problem?
No. If, upon the next visa application or entry, the officer sees that the person had an entry without a corresponding exit the last time, the officer will probably place the burden upon the person to prove that they left on time (e.g. with an entry stamp to another country, or other evidence that places the person in another country on a certain date).
