If the cache is disabled, and the plugin is showing again, then it is a cache issue for sure.
There is no visual cache in the plugin – that cache is only used for the ajax requests. We are using W3TC on our demo site as well without any problems.
I have an idea though. It is possible, the cache is not keeping separate files for different browsers, so a fallback version of the page might be shown. Try turning off this option right here. It may have triggered the default search to show on old user agents, or it missidentified a browser, but would explain the problem perfectly.
It is very unlikely, however I don’t see any other possibility for the random behaviour.