An important note to start: the "Links Database" is a table named "Links" that lives inside a Sitecore database. It is not a separate database.
Sitecore only updates the Link Database on the database referenced by the CM server. The Sitecore Scaling Guide (section 3.6.1) states it as follows:
In a multi-server Sitecore setup, the link database is only
automatically updated for databases that are referenced from the CM
environment.
This client is using the Sitecore Azure module to host, manage, and deploy to its production servers in Azure, including the Sitecore databases. This means that the web roles (where the production CD servers live) have their own versions of every database. This image from the Scaling Guide (section 3.2.1) shows an example of this architecture (without Azure, but accurate enough):

The CD server was looking to its core database, while the CM server was only updating the "on prem" core database. This is why the Links table on the CD's core database was empty. This also explains why we don't see this sort of problem in many of our production environments (usually our CD servers point to the same core database as the CM servers).
Additionally, a site could have the above problem, with CD servers not having access to a built Links database, and have no problems. Much of the standard code we write for Sitecore doesn't need to use the Link database at all.
Again, from the scaling guide:
To ensure that Sitecore automatically updates the link database in the
CD environment: The CD and CM instances must use the same name to
refer to the publishing target database across the environments
(typically Web). One of the following conditions should be met: The
Core database should be shared or replicated between the CM and CD
instances. The Link database data should be configured to be stored in
a database which is shared between CM and CD publishing target
database (typically Web).