How to implement a searchable addresses database (for a form)?
My first approach would be to build a basic importer using the BatchAPI and create a custom entity to hold the address data (NOT a content type), combined with Address Field for proper storage.

Then, I would use Search API and Search API Solr to index and store those entities, afterwhich you can build custom forms with Form API or use Views to expose and search the index - which will be much faster than Drupal db queries. Whenever possible, keep MySQL from doing work, as this is what will bog down your site.

This keeps things close to "Drupal native" while solving many of the performance issues you raised with Solr.

You can use Form API to build forms with #ajax callbacks to query and return data from Search API queries as well.

The import will never be lightning fast unless you're not using the Drupal API to store them as entities. When you don't store them as entities, you lose a lot of the flexibility of say, plugging into Views or Search API without a decent bit of work. You couldn't also add fields with field API, at that point it's just flat data, so say goodbye to easy addition of taxonomy fields or using Address Field.

With Solr constantly indexing new and updated entities, having the import be lightning fast isn't really a priority (IMO) as long as it is reasonable. If you have millions of addresses, Drupal will only be able to parse rows so fast, and a lot of this is due to the event system (save an entity, fields attach, hooks fire, alters fire, etc) on every call to entity_save. The price you pay in speed here is paid off later when you want to manipulate or integrate that data with the contrib space.

The gist I linked to was an experiment I was doing with the Data module and CSV files. This loads the entire CSV file and dumps its contents into MySQL using load infile. This will plant data into a database very quickly, but, as I said, you will have a lot more work trying to get Drupal to recognize, communicate with, and extend that data.

Another approach, totally non-Drupal, would be to import the data to a PostgreSQL (9.4+) database or a no-SQL equivalent, possibly even something like Firebase, and execute searches against that. Then again, this is almost the same as doing Search API + Search API Solr, except you'd have to build the wrappers to create and send queries to those servers. So, it is still valid to offload all of this work in a separate system just to crunch data. It really depends on how much programming you feel like doing.

Just to be clear, there are a handful of options here, it just depends on how much you can stomach if it doesn't use Drupal in some way. Personally, I would not want to give up the flexibility the Drupal API provides in terms of understanding your data model, and therefore, I would create a custom entity and start there. It will be slower, but in the end provide more points of integration for you in the module ecosystem.