I just found a “Rejected cookies” option in W3 Total Cache. W3 Total Cache shouldn’t cache pages that use the specified cookie. So, if your plugin could set a “any-theme-switcher-mobile” cookie when the mobile versions of pages are requested, W3 Total Cache shouldn’t cache them and this issue should be solved. I know this might not work with other WordPress cache plugins but it might be work looking into.
If there’s a cookie already being set by any theme mobile switcher now, maybe I can use that cookie and my problem can be solved. 🙂