Welcome to the Airtable community!
Which API are you using? If you are using the scripting, custom apps, or metadata api, you can get the id of the linked table from the field options of the linked record field. The field options for a linked record field are documented here and here.
Of course, you need to know the current table in order to get field option information. If you have only the record, there is no easy way to tell which table it belongs to.
If you are using only the standard REST API, you cannot get the information from the standard REST API.
I do not know if the Enterprise API has access to base schema metadata, but it might. (I do not have access to the Enterprise API.)
Can you clarify on how you plan to parse every table to identify which table a linked record points to? It is not possible to identify the table from only the record id, unless you try to get that record id from every table in the base, which is a waste of resources.
On the other hand, hardcoding the linked table should not be no more onerous than hardcoding any other table name, as long as the base schema is stable.