Hi again haleeben.
As I said, +200 blogs on W3TC + Varnish working with no problems actually.
Here, some sites on our network to check out (as you can see, the body tags change for each browser, so I'm pretty sure no JS needed for this as @jrevillini patched):
Anyway, take care that W3TC does not work with shared hostings (and also with local ones, imo). Maybe that's why you can't get it to work?
In other hand, as I understand how the cache works, the page is firstly created from scratch and then cached the first time you open it, so the classes are applied before the cache creates it.
Must say that this is a mess. That's why default themes use in-theme filters. :\
PS: Remember there's a bug with IE not working that will be fixed, hoping I get time, this weekend.