Search for first and lastname without order
There are two main components to the question: the searching of the name column and how the data is delivered to the user. As predictive typing is more related to programming, caching, etc. and as Aaron mentioned is not a good idea to do on each keystroke, I will not cover it.

As for how best to query the database:

The logical choice here is Full Text Search, because that provides the exact features you're looking for:


  Full-text queries perform linguistic searches against text data in
  full-text indexes by operating on words and phrases based on rules of
  a particular language such as English or Japanese. Full-text queries
  can include simple words and phrases or multiple forms of a word or
  phrase. A full-text query returns any documents that contain at least
  one match (also known as a hit). A match occurs when a target document
  contains all the terms specified in the full-text query, and meets any
  other search conditions, such as the distance between the matching
  terms.


However, the OP has updated the question to say that the database belongs to another company. So that leaves two main options:


Using a complex setup of the LIKE operator
Creating a localized version of the database and implementing the Full Text Search features.


Option 1


  For example the person I search for is called John Williams: It should
  work with searchstrings like 'John W', 'Williams Jo', 'Will' or 'Joh'


To achieve this, you'd need to split the user's input by spaces (or some other desired delimiter) and dynamically build your WHERE clause based off that in a format like

WHERE ... LIKE '%' @string1 + '%' OR ... LIKE '%' + string2 + '%' OR ...


While possible, this is far from ideal as the LIKE operator is not very efficient when it comes to comparing strings, even if there are only 200,000 rows. It will not scale well and I wouldn't trust it for this use case in a production system:


  In contrast to full-text search, the LIKE Transact-SQL predicate works on character patterns only. Also, you cannot use the LIKE predicate to query formatted binary data. Furthermore, a LIKE query against a large amount of unstructured text data is much slower than an equivalent full-text query against the same data. A LIKE query against millions of rows of text data can take minutes to return; whereas a full-text query can take only seconds or less against the same data, depending on the number of rows that are returned.


Aside from this, you'll have to accommodate users who have special characters (language-specific characters, punctuation), extra spaces, abbreviations, etc. in their input.

Not the "right" choice by any means, but you can probably hack it together if you must.

Option 2

Use replication, mirroring, etc. to get a local copy of the user data and build a Full Text Index on it to leverage all of the features, like a thesaurus, language support, and limiting search results based on rank of relevance which would greatly help your predictive text typing if you still decide to pursue it.

While requiring more up front effort, this is the "right" way to do this.