That is the only possible cause I can think of, it is definitely not related to this plugin. The font-face declaration is made within the search, but cache plugins tend to temper with inlince CSS and move them to files or different sources. I am seeing at least 20 different font-faces loaded within the site header, but the search inline CSS is completely missing.
Try completely turning off all the cache – all cache related plugins and settings to see what happens, it should resolve the issue immediately.