The trick would be to have each user register their own API key.

This seems like such an obvious answer, why isn't it significantly more common?

Because that will also self-select the audience to be really small.

No, not at all. There are ways to implement this without making it a requirement to use the app. For example, you implement a counter for each user of the app, so they can only use a subset of the API requests allowed for your application.

Then if they go over their allocated amount of calls, or they have been a user for X days/weeks/months, you give them a guided walkthrough on how to register their own API key.

I imagine for something like 90%+ of users, a popup that says "Your maximum number of API calls has been reached, click this link and register your own API key to continue using..." is an instant nope

this, I wanted to make a little utility for getting lyrics for whatever song is currently playing on spotify[1] and ran into the issue for getting the song name without using the API since that's just inconvenient for the end user. The most popular such project does go that way though.[2]

I ended up writing a small library that does that locally cross-platform by using the metadata from the app.[3] The approach is probably not as robust as the API, but much faster and works well.

[1] https://github.com/SwagLyrics/SwagLyrics-For-Spotify

[2] https://github.com/johnwmillr/LyricsGenius

[3] https://github.com/SwagLyrics/SwSpotify

The Spotify API doesn't support private API keys, so you need to create your own OAuth App and then authorize it for yourself.

Also, they can lock out out overnight and good luck appealing to the legal team.

How does the nature of the API determine the number of users?

I meant rate limits. Edited my original comment.