I'm having the same problem.
Are you guys using Minify by any chance? I use both plugins and experience this problem.
Remember that disabling WP Super Cache wont actually stop it reading from the cache folder, due to the changes in htaccess.
I found if I clearer the WP Super Cache's cache folder for my test page with minify on CSS, the problem remained. If I disable minify on CSS, flush minify cache, clear WP Super Cache's cache folder then reload the page, the font awesome works correctly. Reload the page so it's definitely loading from cache (WP Super Cache enabled), everything is still fine. So I'm pretty sure it's an issue with Minify.