SIM808 registration denied for new SIMs
I got some help from an Aeris engineer with this one.

It turns out that when a SIM first registers with the network, it requires better signal quality than subsequent registrations. When the SIM has successfully registered with the network the first time, some information is stored on the SIM that allows it to register easier the next time.

Mobile phones have highly integrated radios that allow them to dynamically adjust the antenna gain as needed. The reason my Android phone could do the first registration and the SIM808 could not, is likely because the Android phone was maxing out it's antenna gain and therefore was receiving the network signal better than the more primitive antenna on the SIM808

To prove this to myself, I spent some time on cellmapper.net and found out where the T-Mobile 2G tower is in my town. After driving close to it, I was able to register a brand new SIM the first time with my SIM808

I also had this same behavior with a hologram.io SIM