Долго пытался понять как Вы так сами себя обманули? :) мемкеш попутал? Его из этого уравнения лучше вообще удалить, т.к. он ничего не меняет. Проблема остается в том же точке где и была - нжинкс ни при первом ни при втором обращении не знает кто к нему пришел, поэтому невозможно добавить этот признак в ключ кэширования и разделить кэш на мобильный и немобильный.
Почему ни чего? Что мешает определить клиента тем же php-mobile-detect
(или там browscap) из php, поместить результат в memcached и при
следующих запросах его уже брать nginx-ом?