I was using a wifi connection with a stackexchange site and entering a new post. I kept entering different tags and no suggestions and I was getting suspicious. I knew I used one of the tags before. I moved to another location and the suggestions started showing up. OK so it's a network issue. The laptop connection LED is on all the time but the browser was still having issues with the web service.
show some kind of progress bar when typing so the user knows there's some background processing happening.
keep showing something like 'nothing found' while entering partial tags until some tag is found.
(your idea here)