Fastest way to search a SQLite database thousands of times?

This may be one of those cases where you may need to try different approaches and then see if each is fast enough. As @Philip suggested indexes would be a good starting point, if you don't already have an index on at least postcode this should significantly improve performance.

If you already have this or want to try for further gain I would consider loading the Excel data into your SQLite database and trying the do this as one big query (it will need to do a full table scan of everything due to the number of matches that you are trying to get, but doing this once may not be too bad.

If this is not getting the results you want or proving to difficult to get the query right you could try loading all of the SQLite data into Python and build into dictionaries that will sort the data by what you need to look up e.g. one level of dictionary for the countries, within each country have all of the postcodes, within each postcode have a list of all of the records for that country / postcode.

Basically, the theme of this is make sure you are doing your look ups against hash table type structures (sorted key-value pairs such as database indexes, a python dictionary etc.) or if you do go through record by record don't do this for each record in your other dataset.

For misspelling detection, you can look at phonetic algorithms (but each is made only for a particular language) because especially the LIKE '%city%' will remain inefficient even with indexes.

Additionally you can try to reorder excel data by country (first ask for DE, then US, ...). So Sqlite can "concentrate" on one table and doesn't have to switch all the time, moreover the prepared statement cache of Python's Sqlite-wrapper works more efficiently.

EDIT:

A prepared statement is a previously parsed and analyzed SQL-statement. Executing it multiple times is more efficient than creating and preparing a new statement all the time. Python's Sqlite-wrapper caches some prepared statements and reuses them if the exactly same SQL-statement string is used again.