How to "self audit" all of the SQL Server licenses at an organization? So I have started a new job with a nice non-profit organization, which has been around for a few decades. They have a wide variety of SQL Server editions and versions (ex: 2005 Express to 2016 SP2 Enterprise) and across many Windows VMs (versions anywhere from 2003 to 2016). 

The previous DBAs did not complete any documentation around the number of licenses the company owns, nor editions, versions. Effectively no useful records.

I have run the MAP toolkit to gather details on the SQL Servers. So at least I've got a starting point for what servers exist, and I've dug into which are still serving up production data. 

I have also used the new ApexSQL Discover tool with mixed results (sorry guys I love your stuff but I can't wait 3 days for this tool to run when I need to add 1 server). And also dbatools find-dbainstance (not a huge fan of using PS to export large amounts of data). So by piecing this all together, I'm fairly certain at this point that I've discovered most or all of the instances that ever existed on this domain.

Of course, I've queried the licensing in a number of ways and thoroughly examined the completely useless extremely helpful MS SQL licensing guide of which nothing seems to provide any information on the licenses that the organization owns or how to acquire it.

The crux of the issue: Some of these licenses were purchased a decade (or two) ago. Some were surely paper invoices. Remember I mentioned this is a non-profit? On the plus side, licensing is cheap. On the other hand, licensing is cheap, so most or all of the licenses do not have SA because it's cheaper to buy new ones. edit: This was the reasoning at the time for not purchasing SA, I was not involved.

Should I just assume that since most likely none have SA--that the server is also likely to be licensed properly--and just buy new ones as needed? That seems like a horrible approach.

My question:

How the heck do I know what SQL Server licenses my new company owns without trying to dig up paper invoices from 2004? I've never been in this situation before. Is my only option to get audited or pay for a partner to audit? (and if so, Microsoft what is you doin' bb??). 

Any insights that dba.se can provide here will probably add years to my life. Thanks all!
[…] 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.