Rodrigo,
A primeira consulta:
SELECT COUNT(*) FROM tabela_de_clientes
Você está contando apenas os registros de uma única tabela (tabela_de_clientes);
Quando você executa a segunda consulta:
SELECT A.matricula, A.nome, COUNT(*) FROM
tabela_de_vendedores A
INNER JOIN notas_fiscais B
ON A.matricula = B.matricula
GROUP BY A.matricula, A.NOME;
Você esta associando (JOIN) os registros de duas tabelas distintas (tabela_de_vendedores com notas_fiscais). Nesse caso quando as matriculas de cada tabela são iguais (ON A.matricula = B.matricula)
Provavelmente a tabela de notas_fiscais contém N notas para 1 vendedor por exemplo. Por isso a contagem deve ser alta.
Caso você queira obter a quantidade total de notas fiscais por vendedor, tente usar LEFT JOIN por exemplo.
Existem diversos tipos de "JOINS" que podem ser utilizados. (INNER JOIN, LEFT JOIN, RIGHT JOIN, OUTER JOIN, FULL OUTER JOIN, CROSS JOIN) [Obviamente dependendo do banco de dados utilizado]