Via Jan Lehnardt (plok) he encontrado el siguiente código PHP que define una clase muy básica para recibir peticiones REST. Si luego se usan la función json_encode de PHP5 para codificar en ese formato, se consiguen todas las ventajas de uso en el cliente con el mínimo código.

/*
Public domain PHP REST Controller Base Class.
Originally by Jan Lehnardt 
Usage instructions: http://jan.prima.de/~jan/plok/archives/115-REST-Controller-for-PHP-Applications.html
*/

class REST_Controller extends Controller
{
  var $method = 'get'; //default
  function REST_Controller() {
    parent::Controller();
  }
  function _dispatch($id = false)
  {
    if(isset($_SERVER['REQUEST_METHOD'])) {
      $this->method = strToLower($_SERVER["REQUEST_METHOD"]);
    }
    $dispatch_method = "_{$this->method}";
    if(!is_callable(array($this, $dispatch_method))) {
      $this->_respondError("501 Not Implemented");
      return false;
    }
    $this->{$dispatch_method}($id);
  }

  function _getProtocol()
  {
    $protocol = "HTTP/1.1";
    if(isset($_SERVER['SERVER_PROTOCOL'])) {
      $protocol = $_SERVER['SERVER_PROTOCOL'];
    }
    return $protocol;
  }

  function _respondError($error)
  {
    $protocol = $this->_getProtocol();
    header("$protocol $error");
  }

  function _respond($body, $headers = array())
  {
    foreach($headers AS $header => $value) {
      header("{$header}: {$value}");
    }
    echo $body;
  }

}