Symptoms
Picker control takes a very long time (2 - 3 minutes) and sometimes times out when filtering for results
Diagnoses
It seems all the filters that can be searched for were switched on in K2 Designer (on control level).
Resolution
By only filtering for Name and/or Displayname the waiting time has been reduced to a few seconds.
There is also a FQN filter which is not natively supported by AD, which means K2 will have to return ALL entries in AD and filter through the results by itself to find the search query. By disabling the FQN filter you can dramatically reduce the waiting time for a picker control.
I recommend to only use Name, Displayname and optionally Email as filters.