Isso é o que acontece com uma chave primária composta que incorpora um auto_increment. Recrie a chave primária para que seja puramente seu campo auto_increment (empId) e crie um índice exclusivo em companyId e empId

EDITAR

Observe que isso se aplica apenas às tabelas MyISAM e BDB. Se você usasse o InnoDB para suas tabelas, também funcionaria como você queria