Varnish + Adaptive Theme
Do you perhaps use Context Breakpoint? I had a similar experience using that module. The module states the following on its project page: 


  Caching implications
  
  This module has implications for using the Drupal page cache. Check the README.txt under CACHING for a detailed
  explanation and possible solutions.
  
  A more detailed explanation is in the README.


I ran into the same situation and it is caused by the way Drupal 7 caches content. It only checks the URL. So if you were to open a page on a mobile phone, which already existed in cache, you will receive the desktop version. 

The inverse is also true. If cache is emptied or outdated and the next user to request the page is using a mobile phone, that user will make sure the mobile version is stored in the cache and served to desktop users.

This is certainly true for Drupal's internal caching system, and disabling the Cache pages for anonymous users option solves the problem. 
An alternative could be to use Context Mobile Detect. Which does seem to play nice with Drupal's page cache.