How to "self audit" all of the SQL Server licenses at an organization?
[…] nothing seems to provide any information on the licenses that the organization owns or how to acquire it.
How the heck do I know what SQL Server licenses my new company owns […]

If you have a Premier Agreement
This is fairly straight  forward, you will have an Account Manager assigned (TAM) which can pull up any licensing information given to Microsoft (assuming it was bought through a licensed 3rd party or part of your Premier contract).
From the above you can then divvy out the licenses as needed/used based on your environment.
If you don't have a Premier Agreement
In this case you'll need to log-in/contact/find all records related to licensing on your own. This might mean looking for paper records from 2004 as you've suggested, contacting whatever 3rd party reseller of licensing you went through in those periods of time, or tracking down POs to find out if anything was bought and where it was bought.
The last ditch possibility under this item is to setup a time to speak with a licensing specialist or a Microsoft account representative to see if they can pull anything from previous agreements of years. Note that if you don't have SA, then the licenses may not be applicable to your environment. Also note there are older style licenses that also may no longer be applicable to the environment.

[…] most or all of the licenses do not have SA because it's cheaper to buy new ones.

SA gives other benefits than just being allowed to be at any version. It mainly focuses benefits around license mobility, HA/DR, virtualization, and hybrid scenarios. It's also generally cheaper than buying net new licenses.