It calls some of these stateless, but don't they all have to run a secondary look-up?

For example, in Basic Authentication, you still have to check the username and password against a database, whether that be a file, a relational database, LDAP, etc. For JWT, to verify the signature you must look up the issuer's pre-shared or public key.

Is it even possible for a request be stateless if it requires authentication?