How do I get an elastic IP address un-locked without premium support?

Since you've managed to attach and detach the EIP successfully, it clearly isn't associated with any resource. The likeliest explanations would be either that a reverse DNS record would be configured, which you checked already, or that AWS support would've locked the EIP to your account based on an earlier request. The latter option in mentioned in this documentation article: https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/Using_Elastic_Addressing_Reverse_DNS.html

I suggest you double check that a reverse DNS record doesn't exist for the EIP with the aws ec2 describe-addresses-attribute --allocation-ids eipalloc-123456 --attribute domain-name CLI command (https://awscli.amazonaws.com/v2/documentation/api/latest/reference/ec2/describe-addresses-attribute.html), and if not, then raise a support ticket to get the address released.

I think support will probably accept the request under the "Account and billing" option also available without Enterprise or Business Support, since it's directly connected to a service you are charged for: https://docs.aws.amazon.com/awssupport/latest/user/case-management.html