Что является более серьезной проблемой: наличие избыточных данных или получение более одного результата для запроса?
Если первое - это проблема, значит, у вас есть неприятный вопрос параллелизма, который нужно решить.
Однако, если проблема в последнем, почему бы просто не дать каждому хосту, который хранит значения в memcache, уникальный идентификатор и добавить его к любому ключу?