Na verdade, as duas regex que você indicou não retornam o mesmo resultado (pelo menos no teste que fiz - **JDK 1.7.0_80** - e também é possível vê-las funcionando [aqui][1] e [aqui][2]).

Eu criei um método bem simples, para testar uma regex:

    public void testregex(String input, String regex) {
        Matcher matcher = Pattern.compile(regex).matcher(input);
        if (matcher.find()) {
            System.out.println(matcher.group(1));
        }
    }

Em seguida, testei a mesma entrada usando as duas regex (detalhe que o `\` deve ser escapado, por isso é escrito como `\\`):

    String input = "Detalhamento de Serviços nº: 999-99999-9999";
    testregex(input, "Detalhamento de Serviços.+(\\d+-\\d+-\\d+)");
    testregex(input, "Detalhamento de Serviços\\D+(\\d+-\\d+-\\d+)");

O resultado foi:

    9-99999-9999
    999-99999-9999

Isso acontece porque os quantificadores `+` e `*` [são "gananciosos"][3] e tentam pegar o máximo possível de caracteres. No primeiro caso, ele também pega os dois primeiros dígitos `9`, porque o restante da `String` (`9-99999-9999`) também satisfaz a última parte da regex (`\d+-\d+-\d+`).

No segundo caso, ele não pega os dois primeiros `9` porque `\D` garante que não vai pegar dígitos.

Sendo assim, algumas soluções possíveis são:

- Usar o `\D`: assim, você garante que, por mais que o quantificador seja ganancioso, ele não vai pegar um dígito por engano
- Usar um `?` logo após o quantificador `+`, pois isso [cancela o comportamento "ganancioso"][4]. A regex fica assim: `Detalhamento de Serviços.+?(\d+-\d+-\d+)` - note o uso de `.+?` para remover a "ganância"
- Definir a quantidade de dígitos, usando `{}`. Por exemplo, se a quantidade de dígitos é sempre "3-5-4", você pode usar `Detalhamento de Serviços.+?(\d{3}-\d{5}-\d{4})`. Se a quantidade de dígitos varia, use a sintaxe `{min,max}`. Por exemplo, se há um mínimo de 2 dígitos e máximo de 3, use `{2,3}` (e use o "cancelador de ganância", ou o `\D` para garantir. Adapte de acordo com a sua necessidade.


  [1]: https://regex101.com/r/IncOSL/1
  [2]: https://regex101.com/r/Lukfy3/1/
  [3]: http://www.rexegg.com/regex-quantifiers.html#greedytrap
  [4]: http://www.rexegg.com/regex-quantifiers.html#lazy_solution