Thank you for taking the time to write to us, but this is not
a bug. Please double-check the documentation available at
http://www.php.net/manual/ and the instructions on how to report
a bug at http://bugs.php.net/how-to-report.php

If a fatal error (E_ERROR) is created the engine might be in an unreliable state, we therefore can't all error handlers. Quoting the docs:

"The following error types cannot be handled with a user defined function: E_ERROR, E_PARSE, E_CORE_ERROR, E_CORE_WARNING, E_COMPILE_ERROR, E_COMPILE_WARNING, and most of E_STRICT raised in the file where set_error_handler() is called. "
http://php.net/set_error_handler

According this quote the bug should not occur if specified error types
will not be raised in the file where set_error_handler() is called.
Let's try to move the respective code fragment to the other file:
-- set_error_handler.php --
<?php
$foo = new \Foo\MyErrorHandler();
set_error_handler(array($foo, 'errorHandler'));
set_exception_handler(array($foo, 'exceptionHandler'));
register_shutdown_function(array($foo, 'fatalErrorHandler'));
?>
-- end of set_error_handler.php --
then let's modify slightly the our example:
-- bug --
namespace Foo;

class MyErrorHandler {
  function errorHandler() {
    echo __METHOD__ . "\n";
    throw new \Exception('test');
  }

  function exceptionHandler() {
    echo __METHOD__ . "\n";  // should be called!
  }

  function fatalErrorHandler() {
    echo __METHOD__ . "\n";  // should be called!
  }
}
require_once __DIR__ . '/set_error_handler.php';
require_once __DIR__ . '/not_existing_file.php';  // file should not
exist
die();
-- end of bug --
If you will try to run this example you will get the same invalid
behavior.

Why PHP will not call at least shutdown function in such situtations? Because the engine is in the an unreliable state... What is unreliable state? Is it bug that PHP developers unable to fix due some limitations?

And please note that the bug causes the following handlers will not be called:
1. array($foo, 'exceptionHandler');
2. array($foo, 'fatalErrorHandler');