> For each election, I have to register anew

No. You register once and that applies to all future elections (at least until you update your registration for whatever reason, e.g. because you changed addresses).

> and the agency in charge has a backoffice is cross-checking this against... something?

Against the state's voter registration database, usually maintained by that state's Secretary of State or equivalent.

> What if my birth certificate or whatever is from a different place.

If the birth certificate is from somewhere within the US, then validating the birth certificate is usually just a matter of contacting the county clerk where you were born. If it's from somewhere outside the US, then you ain't eligible to vote anyway unless you've gone through the process of becoming a naturalized citizen — in which case you'd have more appropriate identifying documents that you'd use in place of your birth certificate.