I'm in the process of applying for a work visa - one of the things requested is some kind of authentication that I worked at all the places I say I worked in my work history (that sentence sounded awkward). This isn't really something we do in my home country (usually just a list on a resume or CV is sufficient, nothing official from the work place), and it seems incredibly difficult, if not impossible, to actually get letters from all my former employers (some of them 10 years ago!) certifying that I worked there. Anyone else have this experience?

Most employers HR departments will be able to provide a letter confirming the period of time you worked there (they will have tax records), even if they cannot give any information of your job title (which most can).
If you write to them and let them know why you are asking, when you worked there, which site/dept., your job description, and if you can remember your line managers. This should help them a lot. Your employee or tax number would also help.
Some companies/institutions do not allow managers to give personal recommendations, but will be able to confirm that you worked there.

Any letters they provide should be on headed notepaper. Scans are usually accepted for these letters, but check with the visa office about that. Rules change.

In my home country employers are, if not required, at least strongly suggested to give such letter to each employee when they leave the company. And employees have learned to demand this.

It's especially necessary in environment where companies come and go. I have at least 2 employers in my work history that no longer exist, and would not be able to provide anything retroactively.

It's often nothing more than a paper saying "person X worked in company Y from A to B, his role was D and his responsibilities included E,F and G." signed by the person's manager or HR dept if it's big enough company to have such.

The online system to input these in China is somewhat conflicting. I assume in normal employment the HR will use it, but in my case of own company I was the HR too.

First there is a field to input your work experience in years. So you put (for example) 30 years.

Then there is a place to upload the letters from past empoyers, but it specifically says for last 10 years only.

In my case the office (in Panlong district) wouldn't accept that, and had me change my work experience in first step to 10 years as well to match the letters uploaded.

So based on my experience (autumn 2018), if you fail to produce the letters, your work history is as good as non-existent as far as the work permit is considered.

It's just a reference letter. You should never leave a place without getting one.

With so many applicants (particularly 'teachers') quoting fake references, this certification requirement has become inevitable.

Always get a recommendation letter from your employer, if you deserve one.