Please try using this CVS snapshot:

  http://snaps.php.net/php5-latest.tar.gz
 
For Windows:
 
  http://snaps.php.net/win32/php5-win32-latest.zip

Same behavior in both the latest 5.0.5 and 5.1...

Provide a short but complete reproduce script then.
The code you've pasted in the report is not complete - there is no declaration of MyArray class.

Here's a full code sample to replicate. Note I stripped out the method comments. If you want them I can repost.

<?php
class MyArray extends ArrayObject
{
    function __construct(
        $mValue = array()
        )
    {
        // Convert our value.        
        if(is_array($mValue))
        {
            $mValue = &$this->recurs($mValue);
        }
        elseif(is_object($mValue) && ($mValue instanceof ArrayObject))
        {
            // Get the raw array from our ArrayObject for handling.
            $mValue = &$this->recurs($mValue->getArrayCopy(), $constFlags);
        }
        elseif(null == $mValue)
        {
            $mValue = array();
        }
        elseif(!is_object($mValue))
        {
            // Turn primative into an indexed array.
            $mValue = array($mValue);
        }
        // else - it's an object, enum its public properites.
        
        parent::__construct($mValue);
    }
    
    protected function explodeKeyPath($mKeyPath)
    {
        return explode("/", trim($mKeyPath, "/"));
    }
    
    function offsetSet($mKey, $mValue) 
    {
        $mKey = trim($mKey, "/");
        if(stristr($mKey, "/"))
        {
            // A path was requested. Start out pointing to ourself.
	        $mRetval = $this;
	        
	        $aKeyPathParts = $this->explodeKeyPath($mKey);
                
            // Need to take the LAST path off. That's what we assign our value too. 
            $strLastPathPart = array_pop($aKeyPathParts);
	            
	        foreach($aKeyPathParts as $strPathPart)
	        {
	            // We know we our data are either a primative type or an ArrayAccess. 
	            if(($mRetval instanceof ArrayAccess) && 
	                array_key_exists($strPathPart, $mRetval)
	                )
	            {
	                $mRetval = $mRetval[$strPathPart];
	            }
	            else
	            {
                    // Need a new empty one of us and then point to it!
                    $mRetval[$strPathPart] = 
                        $this->newArrayObject($strPathPart, array(), $this->getFlags());
	                $mRetval = $mRetval[$strPathPart];
	            }
	        }
            
            // Now put our value!
            $mRetval[$strLastPathPart] = $mValue;
        }
        else
        {
	        if(is_array($mValue))
	        {
	            // Need to create a new instance of us!
	            $mValue = $this->newArrayObject($mKey, $mValue, $this->getFlags());
	        }
	        
            parent::offsetSet($mKey, $mValue);
        }
    }

    function offsetGet($mKey) 
    { 
        $mRetval = null;
        
        $mKey = trim($mKey, "/");
        if(stristr($mKey, "/"))
        {
            // A path was requested. Start out pointing to ourself.
	        $mRetval = $this;
	        
	        $aKeyPathParts = $this->explodeKeyPath($mKey);
	            
	        foreach($aKeyPathParts as $strPathPart)
	        {
	            // We know we our data are either a primative type or an ArrayAccess. 
	            if(($mRetval instanceof ArrayAccess) && 
	                array_key_exists($strPathPart, $mRetval)
	                )
	            {
	                $mRetval = $mRetval[$strPathPart];
	            }
	            else
	            {
                    $mRetval = null;
	                
	                break;
	            }
	        }
        }
        else
        {
            $mRetval = parent::offsetGet($mKey);
        }
        
        return $mRetval; 
    } 
    
    function offsetUnset($mKey) 
    { 
        $mKey = trim($mKey, "/");
        if(stristr($mKey, "/"))
        {
            // A path was requested. Start out pointing to ourself.
	        $oArray = $this;
	        
	        $aKeyPathParts = $this->explodeKeyPath($mKey);
                
            // Need to take the LAST path off. That's what we unset. 
            $strLastPathPart = array_pop($aKeyPathParts);
	            
	        foreach($aKeyPathParts as $strPathPart)
	        {
	            // We know we our data are either a primative type or an ArrayAccess. 
	            if(($oArray instanceof ArrayAccess) && 
	                array_key_exists($strPathPart, $oArray)
	                )
	            {
	                $oArray = $oArray[$strPathPart];
	            }
	            else
	            {
                    // Hmmmm... bad path... Die. Nothing will happen below.
                    break;
	            }
	        }
            
            // Now unset our value!
            if(($oArray instanceof ArrayAccess) && 
                array_key_exists($strLastPathPart, $oArray)
                )
            {
                unset($oArray[$strLastPathPart]);
            }
            // else - Bad path.. do nothing...
        }
        else
        {
            parent::offsetUnset($mKey);
        }
    } 

    function offsetExists($mKey) 
    { 
        $bRetval = false;
        
        $mKey = trim($mKey, "/");
        if(stristr($mKey, "/"))
        {
            // A path was asked for. Start at our root.
            $mPathData = $this;
            
	        $aKeyPathParts = $this->explodeKeyPath($mKey);
	            
	        foreach($aKeyPathParts as $strPathPart)
	        {
	            // We know we our data are either a primative type (non-array) 
	            // or an ArrayAccess. 
	            if(($mPathData instanceof ArrayAccess) && 
	                array_key_exists($strPathPart, $mPathData)
	                )
	            {
                    // So far so good... True will remain unless a latter path 
                    // part is invalid. 
	                $bRetval = true;
	                
	                // Set for next loop.
	                $mPathData = $mPathData[$strPathPart];
	            }
	            else
	            {
	                // Nope, bad path.
	                $bRetval = false;
	                break;
	            }
	        }
        }
        else
        {
            $bRetval = parent::offsetExists($mKey);
        }
        
        return $bRetval;
    } 
    
    protected function &recurs(
        $aData
        )
    {
        $aRetval = $aData;
        
        foreach($aRetval as $mKey => &$mValue)
        {
            // If we have a primative array or MyArray-based instance 
            // convert them to us... Buhahahahahah!!!  
            if(is_array($mValue) || 
                (is_object($mValue) && ($mValue instanceof ArrayObject))
                )
            {
                $aRetval[$mKey] = new MyArray($mValue);
            }
            // else - leave it alone!
        }
        
        return $aRetval;
    }
}

$a = array(
    "test" => array(
        "one" => "dunno",
        "two" => array(
            "peekabo" => "do you see me?",
            "anyone" => array("there")
            )
        )
    );
$oArray = new ArrayObject($a);
$oMyArray = new MyArray($a);

$bWorks1 = array_key_exists("test", $oArray);
$bWorks2 = array_key_exists("test", $oMyArray);

$bShouldWorkButDoesNot = array_key_exists("test/two/peekabo", $oMyArray);
$bDirectWorks = $oMyArray->offsetExists("test/two/peekabo");
$bDirectBadPathWorksToo = $oMyArray->offsetExists("test/two/notfound");
?>

Fixed in CVS HEAD and PHP_5_1.

After discussion with Marcus and Andi, this fix is reverted and bug marked as bogus. array_... functions were not designed to work with ArrayAccess interface, ao array_key_exists() shouldn't call ofssetExists() at all.
You should use isset() instead of it.

Ok, isset works as expected. IMHO, the behavior should be made consistent across the one array_key_exists example that works.