Generate path based on menu parent path rather than title

This is not an issue with Pathauto persistent state, but pathauto itself.
The only thing that the token [join-path] will do is use a cleaned version of the titles as path (regardless of parents' aliases)

        case 'join-path':
          module_load_include('inc', 'pathauto');
          $values = array();
          foreach (element_children($array) as $key) {
            $value = is_array($array[$key]) ? render($array[$key]) : (string) $array[$key];
            $value = pathauto_cleanstring($value);
            $values[] = $value;
          }
          $replacements[$original] = implode('/', $values);
          break;

This will not give the expected results if any of the parents has a fixed path alias or is not using [node:title] as URL alias.

There should be an additional token f.e. 'join-path-alias' to do this.

Here is one way to do it:

/**
 * Implements hook_token_info().
 */
function MYMODULE_token_info() {
  $info['tokens']['array']['join-path-alias'] = array(
    'name' => t('Joined path alias'),
    'description' => t('Menu parents\' aliases joined.'),
  );
  return $info;
}

/**
 * Implements hook_tokens().
 */
function MYMODULE_tokens($type, $tokens, array $data = array(), array $options = array()) {
  $replacements = array();

  if ($type == 'array' && !empty($data['array'])) {
    $array = $data['array'];

    foreach ($tokens as $name => $original) {
      switch ($name) {
        case 'join-path-alias':
          module_load_include('inc', 'pathauto');
          $values = array();

          foreach (element_children($array) as $key) {
            // Get the clean string generated by pathauto
            $value = is_array($array[$key]) ? render($array[$key]) : (string) $array[$key];
            $value = pathauto_cleanstring($value);

            // Get the path alias
            $link = menu_link_load($key);
            $path = $link['link_path'];
            $alias = drupal_get_path_alias($path);

            // If there is no path alias, use pathauto clean string
            // If there is a path alias, take only the last part
            $alias = strstr($alias, 'node/') ? $value : preg_replace('/.*\//', '', $alias);

            // If the pathauto clean string is different from the alias,
            // we have a custom alias and we should use it, else, use the clean string
            $values[] = ($alias != $value) ? $alias : $value;
          }
          $replacements[$original] = implode('/', $values);
          break;
        }
     }
  }
  return $replacements;
}

I believe you want the [node:menu-link:parent:url:path] you mentioned in the above you used it, but that it only used the menu title. If that's not the case when using that token, then it's a bug in Token module's implementation.

Thank you Dave, you're right, it does exactly what I want!