По моему у вас большая проблема с архитектурой.
Но раз вы сказали, что архитектуру поменять не представляется возможным, то, при условии что известен максимальное значение ключа, вариант может быть такой (но он сверх-неоптимален):
do {
$str = $m->get(rand(0,$max_key_number));
} while (!$str)
echo $str;