I suppose you could derive a key like that, but then is it still a "natural" key? What's the benefit over just having a completely arbitrary key?

I'd argue for a surrogate key in this case because I wouldn't want someone to be parsing my id, and having to worry about changes and backwards compatibility.

E.g., the key might be 2360108 where 236 is company number. Then as we grow eventually you get an id like 10910249, which is ambiguous (company 109 grew to over 10,000 or company 1091?)

I deliberately choose a short prefix for illustration, but this could be an issue with any scheme (you'll never perfectly predict all the future requirements), which using surrogate keys completely avoids.

To be clear, I'm not proposing that the company and employee numbers be concatenated into a single column: I'm saying you could have a composite key, comprising the company number column and the employee payroll number column. This would still be a natural key: each component has a meaning outside the system (company numbers appear on company filings and other formal documentation, employee payroll numbers appear on payslips and are communicated to the tax authorities), and the two in combination have a clear business meaning.

Of course, you may still want to use a surrogate key for performance or security or other technical reasons, as the article describes.

I just wasn't clear on how the specific scenario you laid out made any additional case for their use.