Isso está documentado no wiki do Ubuntu . É definido por padrão para reduzir o número de dependências nos pacotes, mas como você descobriu isso significa que a ordem das bibliotecas é significativa: você precisa garantir que os objetos (de qualquer tipo) apareçam antes das bibliotecas que eles usam .
Você pode desativar isso com --no-as-needed
.