From the memcached mailing list:
"The flush has a one second granularity. The flush will expire all items up to the ones set within the same second."
It is imperative to wait at least one second after flush() command before further actions like repopulating the cache. Ohterwise new items < 1 second after flush() would be invalidatet instantaneous.
Example:
<?php
$memcache->flush();
$time = time()+1; //one second future
while(time() < $time) {
//sleep
}
$memcache->set('key', 'value'); // repopulate the cache
?>