the Memcache::delete(key) function is broken on several combinations of memcached+pecl-memcache combinations. 
pecl-memcache 2.2.5 + memcached 1.4.2 - Memcache::delete(key) WORKS
pecl-memcache 2.2.5 + memcached 1.4.3 - Memcache::delete(key) DOES NOT WORK
pecl-memcache 2.2.5 + memcached 1.4.4 - Memcache::delete(key) WORKS
pecl-memcache 2.2.5 + memcached 1.4.5 - Memcache::delete(key) WORKS
pecl-memcache 3.0.4 + memcached 1.4.2 - Memcache::delete(key) WORKS
pecl-memcache 3.0.4 + memcached 1.4.3 - Memcache::delete(key) DOES NOT WORK
pecl-memcache 3.0.4 + memcached 1.4.4 - Memcache::delete(key) DOES NOT WORK
pecl-memcache 3.0.4 + memcached 1.4.5 - Memcache::delete(key) DOES NOT WORK

According to the documents, $timeout is not required, but for me if I did not include it regardless of value, it fired an error. I made a simple fix for it.
<?php
class memcache_tools extends memcache
{
 public function delete($key, $expire=0)
 {
 parent::delete($key, $expire); 
 }
}
?>

This will force it to behave as it should regardless of version.

I could not get the delete to work properly, so I ended up trying the 'set' method and setting the timeout value to -1.
<?php
$memcache->set('index', 'deleted', 0, -1);
?>

It solved my problem with the delete method.
(using memcached 1.4.5 and pecl-memcache 3.0.6)

In my case this code does NOT work:
<?php
$memcache->set('index', 'deleted', 0, -1);
?>
because of expire == -1.
I set expire = 1 (and I prefer "replace"):
<?php
$memcache->replace('index', '', 0, 1);
?>

Regardless of whether or not it succeeds, for me on Ubuntu 10.04 it always returns false. Just an FYI, you can't seem to rely on the result.