Here is demo using your code and the latest jstree:
http://jsfiddle.net/DGAF4/700/I do not believe it is that slow considering the amount of data you are using.
A few tips though:
1) I do not know which jsTree version you are using - keep in mind there was a version which had search.fuzzy set to true, so set it to false in your config just in case.
2) Also consider limiting searches to 3 chars and up. Searching for a single char will be slow, as it will have to expand almost every branch of the tree - the longer the search term, the faster searching will be.
If that is still too slow - consider moving to lazy loading and server side searches, I doubt drawing and searching in 21000 nodes can be much quicker.
Best regards,
Ivan