It’s essentially for an “is our service is available in your zip code?” yes/no answer so the lookup is trivial.
But the client wants to be able to add and remove zip codes themselves through WP. So, several thousand very short strings need to be stored. How would you set this up? A special content type? A CSV file that would get overwritten every time?
Personally I would rather handle this outside WordPress entirely but if forced to keep inside the WP system, what are the best ideas?
Best practice in my opinion would be a WordPress plugin with a migration for a new table that holds your data.
In your backend you would provide a way to edit the zip codes (and/or add the ability to just import a csv file to overwrite them all, if this makes it easier for your client).
In your fronted you can just query the strings as you wish.
A custom post type is too much overhead and an abuse of the format.