as far as making it async, that's going to be somewhat complex. you have a solid object with lots of keys to iterate; there's no simple way to break the keys into groups and do them in batches, which is the typical async pattern.
i would focus on increasing app performance first.
if you search on every keyup(), you'll have a ton of hits for "e" and other single-letter chars as the phrase is typed.
better to only search when there are 3 or more letters to search for:
if(!s_cache[this.value] && this.value.length>2 ){
also, test() is ~250% faster than match(), and since you don't need the matches, you won't miss the different output:
if( regexp.test ( list[i] ) ){
finally, if you don't need the case-insensitive search, or you can toLowerCase() everything before the search, you can make it about 20X faster (than the 2.5X faster code) using "".split(strWhat).join(strRep) instead of "".replace(rxWhat, srtRep)...
those optimizations should remove the performance problems in real-world conditions that led you to seek a complex async answer.