Но кеш не предназначен для хранения данных. Нафига вы там что-то храните? Так сложно поставить какой-нибудь редис или что-нибудь в этом роде? Или, что еще проще — сделайте в MySQL базу данных с типом MEMORY, она работает, говорят, со скоростью, аналогичной мемкешу.
Также, вопрос! Если вы работаете через UDP, там нет ограничений на размер пакета и размер данных?
Сам мемкеш трет ключи либо когда истекает время хранения, либо когда его попросят, либо когда заканчивается память. Так что скорее всего баг в вашем коде, ну что — пишите в лог все обращения к мемкешу и потом разбирайте этот лог и смотрите, где накосячили.